Submission #744362

#	Time	Username	Problem	Language	Result	Execution time	Memory
744362		amirhoseinfar1385	Permutation (APIO22_perm)	C++17	89.14 / 100	5 ms	468 KiB

perm

//#include "perm.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long>pw;

vector<int>solve(long long k){
	//cout<<k<<endl;
	if(k==0){
		return {};
	}
	if(k==1){
		return {0};
	}
	if(k==2){
		return {1,0};
	}
	if(k==4){
		return {1,2,0};
	}
	if(k==5){
		return {0,2,1};
	}
	if(k==6){
		return {2,3,0,1};
	}
	if(k==7){
		return {0,1,2};
	}
	if(k==8){
		return {1,2,3,0};
	}
	for(int i=1;i<62;i++){
		if(pw[i]==k){
			vector<int>ret;
			for(int j=0;j<i;j++){
				ret.push_back(j);
			}
			return ret;
		}
	}
	int last=0;
	for(int i=1;i<62;i++){
		if(pw[i]<=1e9){
			if(pw[i]*pw[i]<=k){
				last=i;
			}
			else{
				break;
			}
		}
		else{
			break;
		}
	}
	//cout<<last<<endl;
	vector<int>ghabl,bad,now,ret;
	long long dis=(k+1)/(pw[last]+1);
	long long ferghabl=dis-1,ferbad;
	ghabl=solve(ferghabl);
	ferbad=k+1-(pw[last]+1)*dis;
	bad=solve(ferbad);
	for(int i=0;i<last;i++){
		now.push_back(i);
	}
	int szbad=bad.size();
	int szghabl=ghabl.size();
	for(auto x:ghabl){
		ret.push_back(szbad+x);
	}
	for(auto x:now){
		ret.push_back(x+szghabl+szbad);
	}
	for(auto x:bad){
		ret.push_back(x);
	}
	return ret;
}

vector<int> construct_permutation(long long k)
{
	k--;
	pw.resize(62);
	for(int i=0;i<62;i++){
		pw[i]=(1ll<<i)-1;
	}
	vector<int>res=solve(k);
	//for(auto x:res){
	//	cout<<x<<" ";
	//}
	//cout<<endl;
	return res;
}

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