Submission #744503

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744503	2023-05-18T15:53:07 Z	amirhoseinfar1385	Permutation (APIO22_perm)	C++17	91.3333 / 100	479 ms	24420 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct

Subtask #2

81.333333333 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	5 ms	668 KB	Output is correct
4	Correct	22 ms	1684 KB	Output is correct
5	Partially correct	209 ms	10912 KB	Partially correct
6	Correct	257 ms	13276 KB	Output is correct
7	Partially correct	340 ms	18876 KB	Partially correct
8	Partially correct	479 ms	24420 KB	Partially correct
9	Correct	2 ms	340 KB	Output is correct
10	Partially correct	14 ms	1252 KB	Partially correct
11	Partially correct	450 ms	23112 KB	Partially correct
12	Partially correct	368 ms	20512 KB	Partially correct
13	Partially correct	392 ms	20800 KB	Partially correct