Submission #1114067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114067		PieArmy	Permutation (APIO22_perm)	C++17	90.33 / 100	3 ms	516 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 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