Submission #1202489

#TimeUsernameProblemLanguageResultExecution timeMemory
1202489trashaccountPermutation (APIO22_perm)C++20
80.97 / 100
285 ms980 KiB
#include "perm.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define isz(a) (int)(a).size() const int NM = 90, MX = 1e9; const ll LIM = 1e18; ll dp[NM+5], bit[NM+5]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void update(int x, ll val){ while (x <= NM){ bit[x] += val; x += x & (-x); } } ll get(int x){ ll res = 0; while (x > 0){ res += bit[x]; x -= x & (-x); } return res; } ll calc(vector <int> &p){ memset(dp, 0, sizeof(dp)); memset(bit, 0, sizeof(bit)); for (int i = 0; i < isz(p); i++){ dp[i] = 1+get(p[i]); update(p[i]+1, dp[i]); } ll res = 1; for (int i = 0; i < isz(p); i++) res += dp[i]; return res; } vector <int> solve(ll k){ int sz = 1; while ((1LL<<sz) < k) sz++; vector <int> p = {}, pbest = {}; ll best = -1; for (int i = 0; i < sz; i++) p.push_back(i); for (int iter = 1; iter <= 100 || best == -1; iter++){ shuffle(p.begin(), p.end(), rng); ll tmp = calc(p); if (tmp <= k){ if (tmp > best){ best = tmp; pbest = p; } } } p = pbest; while (true){ bool chk = 0; for (int i = 0; i+1 < sz; i++){ if (p[i] < p[i+1]) continue; swap(p[i], p[i+1]); if (calc(p) > k) swap(p[i], p[i+1]); else chk = 1; } if (!chk) break; } ll res = calc(p); if (res == k) return p; vector <int> q = solve(k-res+1); for (int &x : p) x += isz(q); for (int x : q) p.push_back(x); return p; } vector <int> construct_permutation(ll k){ if (k <= 90){ vector <int> res = {}; for (int i = k-2; i >= 0; i--) res.push_back(i); return res; } return solve(k); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...