Submission #1202960

#TimeUsernameProblemLanguageResultExecution timeMemory
1202960KavelmydexPermutation (APIO22_perm)C++20
79.68 / 100
5 ms1092 KiB
/* k--; seperate (k-1) to the sum of (2^i-1) ========================== ========================== */ #include "perm.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define vi vector<ll> #define pi pair<ll,ll> #define pb push_back #define sz(x) ((ll)x.size()) #define sp ' ' #define endl "\n" #define all(x) (x).begin(),(x).end() #define rep(i,x,n) for(ll i=x; i<=n; ++i) #define For(i,n) rep(i,0,n-1) #define ff first #define ss second #define ld long double #define mp make_pair const int N=100,OO=2e9,mod=1e9+7; const int dx[]{0,0,-1,1}, dy[]{1,-1,0,0}; void cmn(int &a,int b){a = min(a,b);} void cmx(int &a,int b){a = max(a,b);} ll p[N], h[N][2]; vector<int>construct_permutation(ll k){ k--; ll n=0; p[0]=1; vector<int>ans; vi v{0}; for(int i=1;i<=59;++i) p[i]=p[i-1]*2,v.pb(p[i]-1), h[i][0]=h[i][1]=0; for(int i=59;i>=1;--i){ while(k>=v[i]){ h[i][0]++; n+=i; k-=v[i]; } if(i>=2){ while(k>=v[i]-p[i-2]){ k-=v[i]-p[i-2]; n+=i; h[i][1]++; } } } assert(!k); n--; for(int i=1;i<=59;++i){ For(j,h[i][0]){ vi toadd; for(int k=0;k<i;++k) toadd.pb(n--); reverse(begin(toadd),end(toadd)); for(int x:toadd)ans.pb(x); } if(h[i][1]){ assert(h[i][1]==1); vi toadd; For(k,i) toadd.pb(n--); reverse(begin(toadd),end(toadd)); swap(toadd.back(),toadd[toadd.size()-2]); for(int x:toadd) ans.pb(x); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...