# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
726534 | 2023-04-19T03:52:03 Z | abcvuitunggio | Permutation (APIO22_perm) | C++17 | 365 ms | 612 KB |
#include "perm.h" #include <bits/stdc++.h> using namespace std; vector <int> construct(long long k, int base){ vector <int> v; multiset <long long> s; for (int i=0;i<base;i++){ v.push_back(0); s.insert(1); k--; if (!k) return v; } v.pop_back(); while (k){ int res=-1; long long sum=0; for (auto i:s){ if (sum+i>k) break; sum+=i; res++; } k-=sum; v.push_back(res); s.insert(sum); } return v; } std::vector<int> construct_permutation(long long k) { if (k==1) return {}; if (k==2) return {0}; int ch[1001]; memset(ch,0,sizeof(ch)); vector <int> ve; vector <int> res; if (k%2==0){ res=construct_permutation(k/2); res.push_back(res.size()); return res; } if (k%3==0){ res=construct_permutation(k/3); res.push_back(res.size()+1); res.push_back(res.size()-1); return res; } int mn=10000; for (int i=2;i<=20;i++){ ve=construct(k,i); if (mn>ve.size()){ mn=ve.size(); swap(res,ve); } } for (int i=res.size()-1;i>=0;i--){ int cnt=0; res[i]++; while (res[i]){ cnt++; if (!ch[cnt]) res[i]--; } res[i]=cnt-1; ch[cnt]=1; } vector <int> res2=construct_permutation(k/2); res2.push_back(res2.size()); for (int &i:res2) i++; res2.push_back(0); return (res.size()>res2.size()?res2:res); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 4 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 4 ms | 212 KB | Output is correct |
3 | Correct | 18 ms | 368 KB | Output is correct |
4 | Correct | 36 ms | 436 KB | Output is correct |
5 | Correct | 136 ms | 556 KB | Output is correct |
6 | Correct | 123 ms | 468 KB | Output is correct |
7 | Correct | 195 ms | 596 KB | Output is correct |
8 | Correct | 321 ms | 552 KB | Output is correct |
9 | Correct | 299 ms | 576 KB | Output is correct |
10 | Correct | 365 ms | 580 KB | Output is correct |
11 | Correct | 315 ms | 588 KB | Output is correct |
12 | Correct | 237 ms | 600 KB | Output is correct |
13 | Correct | 351 ms | 612 KB | Output is correct |