This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
vector<int> construct_permutation(ll k){
k--;
vector<int>res;
int one=0;
for(int i=0;i<60;i++){
if(pie(i)&k)one++;
}
if(one>30){
int l=0,r=-1;
while(k){
if(k&1){
k>>=1;
res.pb(r--);
}
else{
k--;
res.pb(l++);
}
}
int n=res.size();
for(int &x:res){
if(x<0)x+=n;
}
reverse(res.begin(),res.end());
return res;
}
else{
int l=0,r=-1;
while(k){
if(k&1){
k>>=1;
res.pb(r--);
}
else if(k&2){
k>>=1;
int a=1,b=0;
while(k&1){
a++;
k>>=1;
}
if(k){
while((k&1)==0){
b++;
k>>=1;
}
k--;
}
else a--;
b+=a;
for(int i=a-1;i>=0;i--){
res.pb(l+i);
}
l+=a;
for(int i=0;i<b;i++){
res.pb(r--);
}
}
else{
k-=2;
res.pb(l++);
res.pb(l++);
}
}
int n=res.size();
for(int &x:res){
if(x<0)x+=n;
}
reverse(res.begin(),res.end());
return res;
}
}
/*
int main(){
ll n;cin>>n;
vector<int>ans=construct_permutation(n);
cout<<ans.size()<<endl;
for(int x:ans)cout<<x<<" ";
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |