#include "bits/stdc++.h" #include "light.h" using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif using ll = long long; #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back const ll inf = (1LL) << 62; const ll L = 60; ll n; vector<ll> pos(L); vector<ll> s(L); vector<ll> pot(L+1); ll sz(int k) { if (pos[k] == inf) return 0; return pot[k]; } void prepare() { debug(inf); n = 1; pot[0] = 1; for (int i = 1; i <= L; ++i) pot[i] = pot[i-1] * 2; for (int k = 0; k < L; ++k) { pos[k] = 2 - (pot[k+1] - 1); } debug(pos); } vector<ll> make() { cerr << "make \n"; vector<ll> ret; ll rest = 1; for (int k = 0; k < L; ++k) { s[k] = min(s[k], pot[k] - rest); rest += sz(k); } for (int k = 0; k < L; ++k) { if (pos[k] == inf) continue; ll last = pos[k] + pot[k]; cerr << "adding from bucket " << k << '\n'; for (int l = 0; l <= k; ++l) { if (pos[k] + s[k] >= last - pot[l] && last - pot[l] <= n && last - pot[l] >= 1) { ret.eb(last - pot[l]); cerr << "add " << last - pot[l] << endl; } } if (pos[k] + s[k] >= 1 && s[k] <= pot[k] - 1 && pos[k] + s[k] <= n) { cerr << "add " << pos[k] + s[k] << endl; ret.eb(pos[k] + s[k]); } } ret.eb(1); sort(all(ret)); auto last = unique(all(ret)); ret.erase(last, ret.end()); return ret; } pair<ll, vector<ll>> join(ll p) { n += p; for (int k = 0; k < L; ++k) if (pos[k] != inf) pos[k] += p; return {p, make()}; } ll fix_back(ll p) { cerr << "fix back \n"; int k = 0; ll c = 0; while (c + sz(k) <= p) { cerr << "deleting T(" << k << ") with size = " << sz(k) << endl; c += sz(k); pos[k] = inf; s[k] = 0; k++; } if (c == p) { for (int l = k; l < L; ++l) if (pos[l] != inf) s[l] = min(pot[l], s[l] + c); return 0LL; } ll posk = pos[k]; for (int l = k-1; l >= 0; --l) { pos[l] = posk; posk += pot[l]; } pos[k] = inf; s[k] = 0; for (int l = 0; l < L; ++l) if (pos[l] != inf) s[l] = min(pot[l], s[l] + c + 1); return p - c - 1; } pair<ll, vector<ll>> leave(ll p) { ll t = p; n -= p; cerr << "leave " << p << endl; while (p) { p = fix_back(p); } for (int l = 0; l < L; ++l) if (pos[l] != inf) pos[l] -= p; return {t, make()}; }