| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1360601 | DanielPr8 | Permutation (APIO22_perm) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
deque<ll> solve(long long k){
deque<ll> ans;
if(k==1)return ans;
if(k%2==0){
ans = solve(k/2);ll n = ans.size();
ans.pb(n);
return ans;
}
if(k%3==0){
ans = solve(k/3);ll n = ans.size();
ans.pb(n+1);
ans.pb(n);
return ans;
}
if(k%5==0){
ans = solve(k/5);ll n = ans.size();
ans.pb(n+1);
ans.pb(n+2);
ans.pb(n);
return ans;
}
if(k%11==0){
ans = solve(k/11);ll n = ans.size();
ans.pb(n+4)
ans.pb(n+1);
ans.pb(n+2);
ans.pb(n);
ans.pb(n+3);
return ans;
}
if(k%7==0){
ans = solve(k/7);ll n = ans.size();
ans.pb(n+3);
ans.pb(n+2);
ans.pb(n+0);
ans.pb(n+1);
return ans;
}
if(true){
ans = solve(k/2);ll n = ans.size();
ans.pb(n);
if(k%2==1)ans.push_front(n+1);
return ans;
}
}
std::vector<int> construct_permutation(long long k){
deque<ll> ans = solve(k);
vector<int> ret;
for(ll i:ans)ret.pb(i);
return ret;
}
static long long MX=1e18;
// static bool check_permutation(vector<int> v)
// {
// sort(v.begin(),v.end());
// for(int i=0;i<v.size();i++)
// if(v[i]!=i) return 0;
// return 1;
// }
// long long count_increasing(const vector<int>& v) {
// vector<long long> dp(v.size() + 1, 0);
// dp[0] = 1;
// for (int x : v)
// {
// for (int i = 0; i <= x; i++)
// {
// dp[x+1] += dp[i];
// dp[x+1] = min(dp[x+1],MX+1);
// }
// }
// long long result = 0;
// for (int i = 0; i <= (int)v.size(); i++){
// result += dp[i];
// result = min(result,MX+1);
// }
// return result;
// }
// int main() {
// int t;
// assert(1 == scanf("%d", &t));
// while(t--)
// {
// long long k;
// assert(1 == scanf("%lld",&k));
// vector<int> ret=construct_permutation(k);
// if(!check_permutation(ret))
// {
// printf("WA: Returned array is not a permutation\n");
// exit(0);
// }
// long long inc=count_increasing(ret);
// if(inc!=k)
// {
// if(inc==MX+1)
// printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);
// else
// printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);
// exit(0);
// }
// printf("%d\n",(int)ret.size());
// for(int i=0;i<ret.size();i++)
// {
// printf("%d",ret[i]);
// if(i+1==ret.size())
// printf("\n");
// else
// printf(" ");
// }
// }
// return 0;
// }