SuitNdtie

Bathroom set2

Apr 8th, 2019
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<queue>
  3. using namespace std;
  4. bool debug = false;
  5. struct lenght{
  6.     int l,r,len;
  7.     bool operator < (const lenght& rhs)const
  8.     {
  9.         return len < rhs.len;
  10.     }
  11. };
  12.  
  13. int main()
  14. {
  15.     int T;
  16.     scanf("%d",&T);
  17.     priority_queue<lenght> pq;
  18.     for(int t = 1 ; t <= T ; t ++){
  19.         int n,k;
  20.         scanf("%d %d",&n,&k);
  21.         while(!pq.empty())pq.pop();
  22.         pq.push({0,n+1,n});
  23.         int ansmax,ansmin;
  24.         for(int i=1;i<=k;i++){
  25.             int l = pq.top().l;
  26.             int r = pq.top().r;
  27.             int len = pq.top().len;
  28.             pq.pop();
  29.             int m = (l+r)/2;
  30.             ansmax = r - m - 1;
  31.             ansmin = m - l - 1;
  32.             if(debug)printf("Case %d -> i = %d , (l,r,m) : (%d,%d,%d) , len : %d , ans(%d,%d) \n",t,i,l,r,m,len,ansmax,ansmin);
  33.             pq.push({l,m,m - l - 1});
  34.             pq.push({m,r,r - m - 1});
  35.         }
  36.         printf("Case #%d: %d %d\n",t,ansmax,ansmin);
  37.     }
  38.     return 0;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment