# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
975699 | 2024-05-05T18:06:12 Z | ShaShi | Permutation (APIO22_perm) | C++17 | 1000 ms | 476 KB |
#include "perm.h" #include <bits/stdc++.h> #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define pii pair<int, int> using namespace std; typedef long long ll; const int MAXN = (int)1e6 + 7; const int LG = 60; vector<int> solve1(ll k) { vector<int> res; bool flag = 0; for (int i=LG-1; i>=0; i--) { if (!(k&(1ll<<i))) continue; if (!flag) { for (int j=1; j<=i; j++) res.pb(j); flag = 1; continue; } for (int j=0; j<res.size(); j++) if (res[j] >= i+1) res[j]++; res.pb(i+1); } // for (int i=0; i<res.size(); i++) res[i]--; return res; } vector<int> solve2(ll k) { vector<int> res = solve1(k+1); if (k >= 2 && (k%2) == 0) { vector<int> res2 = solve2((k-2)/2); if (res2.size()+2 < res.size()) { int mx=1; for (int i=0; i<res2.size(); i++) mx = max(mx, ++res2[i]); res2.pb(mx+1); res2.pb(1); swap(res, res2); } } // if (k > 0) { // vector<int> res2 = solve2(k-1); // if (res2.size()+1 < res.size()) { // for (int i=0; i<res2.size(); i++) res2[i]++; // res2.pb(1); // swap(res, res2); // } // } if (k > 0 && (k%2) == 1) { vector<int> res2 = solve2((k-1)/2); if (res2.size()+1 < res.size()) { int mx = 0; for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]); res2.pb(mx+1); swap(res, res2); } } // if (k >= 2 && ((k-2)%3) == 0) { // vector<int> res2 = solve2((k-2)/3); // if (res2.size()+2 < res.size()) { // int mx = 0; // for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]); // res2.pb(mx+2); res2.pb(mx+1); // swap(res, res2); // } // } if (k >= 3 && ((k-3)%4) == 0) { vector<int> res2 = solve2((k-3)/4); if (res2.size()+2 < res.size()) { int mx = 0; for (int i=0; i<res2.size(); i++) mx = max(mx, res2[i]); res2.pb(mx+1); res2.pb(mx+2); swap(res, res2); } } return res; } vector<int> construct_permutation(ll k) { // vector<int> res1 = solve1(k); // if (res1.size() <= 90) return res1; vector<int> res2 = solve2(k-1); for (int i=0; i<res2.size(); i++) res2[i]--; return res2; } // int main() { // ll n = (1ll<<18)-3; // // ll n = 511; // vector<int> res = construct_permutation(n); // cout << res.size() << endl; // for (int i:res) cout << i << " "; // return 0; // }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 2 ms | 348 KB | Output is correct |
4 | Correct | 2 ms | 348 KB | Output is correct |
5 | Partially correct | 12 ms | 476 KB | Partially correct |
6 | Correct | 122 ms | 444 KB | Output is correct |
7 | Correct | 442 ms | 344 KB | Output is correct |
8 | Execution timed out | 1035 ms | 440 KB | Time limit exceeded |
9 | Halted | 0 ms | 0 KB | - |