Submission #744503

#	Time	Username	Problem	Language	Result	Execution time	Memory
744503		amirhoseinfar1385	Permutation (APIO22_perm)	C++17	91.33 / 100	479 ms	24420 KiB

perm

    //#include "perm.h"
    #include<bits/stdc++.h>
    using namespace std;
    vector<long long>pw;
    unordered_map<long long ,vector<int>>mp;
     
    vector<int>solve(long long k){
    	if(mp.count(k)!=0){
    		return mp[k];
    	}
    	//cout<<k<<endl;
    	if(k==0){
    		mp[k]={};
    		return {};
    	}
    	if(k==1){
    		mp[k]={0};
    		return {0};
    	}
    	if(k==2){
    		mp[k]={1,0};
    		return {1,0};
    	}
    	if(k==4){
    		mp[k]={1,2,0};
    		return {1,2,0};
    	}
    	if(k==5){
    		mp[k]={0,2,1};
    		return {0,2,1};
    	}
    	if(k==6){
    		mp[k]={2,3,0,1};
    		return {2,3,0,1};
    	}
    	if(k==7){
    		mp[k]={0,1,2};
    		return {0,1,2};
    	}
    	if(k==8){
    		mp[k]={1,2,3,0};
    		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);
    			}
    			mp[k]=ret;
    			return ret;
    		}
    	}
    	int last=0,mina=10000000;
    	for(int i=1;i<62;i++){
    		if(pw[i]>k){
    			break;
    		}
    		if(pw[i]*pw[i]<k/2000000000){
    			continue;
    		}
    		long long dis=(k+1)/(pw[i]+1);
    		vector<int>fake=solve(dis-1);
    		dis=k+1-(pw[i]+1)*dis;
    		vector<int>fakea=solve(dis);
    		if(i+(int)fake.size()+(int)fakea.size()<mina){
    			last=i;
    			mina=i+(int)fake.size()+(int)fakea.size();
    		}
    	}
    	//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);
    	}
    	mp[k]=ret;
    	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: 81.333333333 / 90