Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- CONSTRUCT A TREE
- 11/21
- ll n,s,cur,mx[MX],co[MX];
- vi ok(int mid) {
- FOR(i,1,n+1) co[i] = 1;
- mx[1] = 1;
- FOR(i,2,n+1) mx[i] = min(n,mx[i-1]*mid);
- cur = n*(n+1)/2;
- int lo = 1;
- for (int i = n; i; i--) {
- while (co[i]) {
- if (cur == s) break;
- while (lo <= n && mx[lo] == co[lo]) lo ++;
- ll des = cur-s;
- ll z = max(i-des,(ll)lo);
- if (z >= i) break;
- co[i] --; co[z] ++;
- cur -= i-z;
- }
- if (cur == s) break;
- }
- if (cur == s) {
- vi CO;
- F0R(i,n+1) CO.pb(co[i]);
- return CO;
- }
- return {};
- }
- int out[MX], ind[MX];
- int main() {
- // you should actually read the stuff at the bottom
- setIO(); re(n,s);
- FOR(i,1,n+1) {
- co[i] ++;
- cur += i;
- }
- if (cur < s) {
- pr("No");
- exit(0);
- }
- int lo = 1, hi = n;
- while (lo < hi) {
- int mid = (lo+hi)/2;
- if (sz(ok(mid))) hi = mid;
- else lo = mid+1;
- }
- if (hi == n) {
- pr("No");
- exit(0);
- }
- // pr(lo); exit(0);
- pr("Yes");
- auto a = ok(lo);
- int t = 2;
- vi depth[MX]; depth[1].pb(1);
- FOR(i,2,n+1) {
- while (!a[t]) t ++;
- depth[t].pb(i); a[t] --;
- }
- /*FOR(i,1,n+1) pr(depth[i]);
- pr(lo);*/
- FOR(i,2,n+1) {
- trav(x,depth[i]) {
- while (out[depth[i-1][ind[i]]] == lo) ind[i] ++;
- cout << depth[i-1][ind[i]] << " ";
- out[depth[i-1][ind[i]]] ++;
- }
- }
- // exit(0);
- // you should actually read the stuff at the bottom
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement