Advertisement
ec1117

Untitled

Nov 21st, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. CONSTRUCT A TREE
  2. 11/21
  3.  
  4. ll n,s,cur,mx[MX],co[MX];
  5.  
  6. vi ok(int mid) {
  7.     FOR(i,1,n+1) co[i] = 1;
  8.     mx[1] = 1;
  9.     FOR(i,2,n+1) mx[i] = min(n,mx[i-1]*mid);
  10.    
  11.     cur = n*(n+1)/2;
  12.     int lo = 1;
  13.     for (int i = n; i; i--) {
  14.         while (co[i]) {
  15.             if (cur == s) break;
  16.             while (lo <= n && mx[lo] == co[lo]) lo ++;
  17.             ll des = cur-s;
  18.             ll z = max(i-des,(ll)lo);
  19.             if (z >= i) break;
  20.             co[i] --; co[z] ++;
  21.             cur -= i-z;
  22.         }
  23.         if (cur == s) break;
  24.     }
  25.     if (cur == s) {
  26.         vi CO;
  27.         F0R(i,n+1) CO.pb(co[i]);
  28.         return CO;
  29.     }
  30.     return {};
  31. }
  32.  
  33. int out[MX], ind[MX];
  34.  
  35. int main() {
  36.     // you should actually read the stuff at the bottom
  37.     setIO(); re(n,s);
  38.     FOR(i,1,n+1) {
  39.         co[i] ++;
  40.         cur += i;
  41.     }
  42.     if (cur < s) {
  43.         pr("No");
  44.         exit(0);
  45.     }
  46.     int lo = 1, hi = n;
  47.     while (lo < hi) {
  48.         int mid = (lo+hi)/2;
  49.         if (sz(ok(mid))) hi = mid;
  50.         else lo = mid+1;
  51.     }
  52.     if (hi == n) {
  53.         pr("No");
  54.         exit(0);
  55.     }
  56.     // pr(lo); exit(0);
  57.     pr("Yes");
  58.     auto a = ok(lo);
  59.     int t = 2;
  60.     vi depth[MX]; depth[1].pb(1);
  61.     FOR(i,2,n+1) {
  62.         while (!a[t]) t ++;
  63.         depth[t].pb(i); a[t] --;
  64.     }
  65.     /*FOR(i,1,n+1) pr(depth[i]);
  66.     pr(lo);*/
  67.     FOR(i,2,n+1) {
  68.         trav(x,depth[i]) {
  69.             while (out[depth[i-1][ind[i]]] == lo) ind[i] ++;
  70.             cout << depth[i-1][ind[i]] << " ";
  71.             out[depth[i-1][ind[i]]] ++;
  72.         }
  73.     }
  74.     // exit(0);
  75.     // you should actually read the stuff at the bottom
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement