# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
984146 | 2024-05-16T10:44:56 Z | vjudge1 | Permutation (APIO22_perm) | C++17 | 0 ms | 0 KB |
//#include "perm.h" #include<bits/stdc++.h> #define sz size() #define ll long long using namespace std; mt19937_64 rnd(990910211394901); vector<int> construct_permutation(ll k) { ll z = 1, sum = 0, d; vector<ll> x; for(ll j = 59; j > 0; --j) { if((z << j) > k) continue; d = j; x.push_back(j); k -= (z << j); break; } ll _k = k; for(ll t = 1; t <= 1000; ++t) for(ll j = 59; j > 0; --j) { if((z << j) - 1 > _k) continue; x.push_back(j); _k -= (z << j) - 1; sum += j; } // for(ll i = 1; i <= 90; ++i) // { // ll t = k - i; // if(t < 2) break; // ll cnt = d; // vector<ll> _x(1, d); // for(ll j = 59; j > 0; --j) // { // if((z << j) > t) continue; // _x.push_back(j); // cnt += j; // t -= (z << j); // } // if(cnt < sum) // sum = cnt, x = _x; // } ll cur = 0; vector<int> ans; for(ll t : x) { for(ll i = cur + t; i > cur; --i) ans.push_back(i - 1); cur += t; } reverse(ans.begin(), ans.end()); return ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); ll n; cin >> n; for(auto i : construct_permutation(n)) cout << i << ' '; }