YEZAELP

JAM: Bathroom Stalls

Jun 16th, 2021
728
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5.  
  6. int main(){
  7.  
  8.     int q;
  9.     scanf("%d", &q);
  10.  
  11.     for(int i=1;i<=q;i++){
  12.         lli n, k, d, l, r;
  13.         scanf("%lld%lld", &n, &k);
  14.         printf("Case #%d: ", i);
  15.         if(n == k){
  16.             printf("0 0\n");
  17.             continue;
  18.         }
  19.         set <lli> data;
  20.         unordered_map <lli, lli> dis;
  21.         data.insert(n);
  22.         dis[n] = 1;
  23.         lli cnt = 0;
  24.         while(true){
  25.             auto it = prev(data.end());
  26.             d = *it;
  27.             cnt += dis[d];
  28.             if(d % 2 == 1) l = r = d/2;
  29.             else {
  30.                 l = d/2;
  31.                 r = d/2-1;
  32.             }
  33.             if(cnt >= k){
  34.                 printf("%lld", max(l, r));
  35.                 printf(" %lld\n", min(l, r));
  36.                 break;
  37.             }
  38.             data.erase(it);
  39.             data.insert(l);
  40.             data.insert(r);
  41.             dis[l] += dis[d];
  42.             dis[r] += dis[d];
  43.         }
  44.     }
  45.  
  46.     return 0;
  47. }
  48.  
RAW Paste Data