Submission #1114070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114070		PieArmy	Permutation (APIO22_perm)	C++17	90.33 / 100	2 ms	336 KiB

perm

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<<" ";
}*/

• Subtask 1: 10 / 10
• Subtask 2: 80.333333334 / 90