| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 974332 | 2024-05-03T08:40:10 Z | IUA_Hasin | Permutation (APIO22_perm) | C++17 | 0 ms | 0 KB |
#include "perm.h"
#include <bits\stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
ll close_pow(ll n){
ll a = 1;
ll b = pow(2, a)-1;
ll ans = 1;
while(n>b){
// cout<<b<<endl;
ans++;
b = pow(2, ans)-1;
if(b>n){
ans--;
break;
} else if(b==n){
break;
}
// cout<<b<<endl;
}
return ans;
}
std::vector<int> dunno(ll n){
std::vector<int> x;
while(n>0){
ll a = close_pow(n);
// cout<<a<<endl;
x.push_back(a);
n = n-pow(2,a)+1;
}
return x;
}
std::vector<int> construct_permutation(long long k)
{
std::vector<int> v = dunno(k-1);
ll sum = 0;
ll pref[v.size()+1];
pref[0] = 0;
for(int i=0; i<v.size(); i++){
sum = sum+v[i];
pref[i+1] = pref[i]+v[i];
}
std::vector<int> ans;
ll ins = sum-1;
ll tempp = 0;
ll temp = v[tempp];
ll cnt = 0;
while(cnt<=sum-1){
for(int i=1; i<=temp; i++){
ll a = ins-temp+i;
ans.push_back(a);
cnt++;
}
ins = ins-temp;
tempp++;
temp = v[tempp];
}
// for(int i=0; i<ans.size(); i++){
// cout << ans[i] << " ";
// }
// cout<<endl;
return ans;
}