Submission #1203000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203000		nouka28	Permutation (APIO22_perm)	C++20	100 / 100	21 ms	328 KiB

perm

#include "perm.h"

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){std::cin.tie(nullptr)->sync_with_stdio(false);}}_;

using ll=long long;

std::vector<int> construct_permutation(long long k)
{
	k--;
	
	auto dfs=[&](auto dfs,ll t)->vector<int> {
		if(t==0)return {};

		if(t%2){
			vector<int> p=dfs(dfs,t/2);
			for(auto&&e:p)e++;
			p.insert(p.begin(),0);
			return p;
		}else{
			if((t-2)%3==0){
				vector<int> p=dfs(dfs,(t-2)/3);
				for(auto&&e:p)e+=2;
				p.insert(p.begin(),0);
				p.insert(p.begin(),1);
				return p;
			}
			if(t>=5&&(t-5)%6==0){
				vector<int> p=dfs(dfs,(t-5)/6);
				for(auto&&e:p)e+=3;
				p.insert(p.begin(),1);
				p.insert(p.begin(),2);
				p.insert(p.begin(),0);
				return p;
			}
			if(t>=4&&(t-4)%5==0){
				vector<int> p=dfs(dfs,(t-4)/5);
				for(auto&&e:p)e+=3;
				p.insert(p.begin(),1);
				p.insert(p.begin(),0);
				p.insert(p.begin(),2);
				return p;
			}
			{
				vector<int> v={0,1,2,3};
				do{
					int cnt=0;
					rep(s,1<<4){
						vector<int> b;
						rep(i,4)if(s>>i&1)b.push_back(v[i]);
						bool flg=1;
						rep(i,(int)b.size()-1){
							if(b[i]>b[i+1])flg=0;
						}
						cnt+=flg;
					}
					if(cnt>=6&&t>=(cnt-1)&&(t-cnt+1)%cnt==0){
						vector<int> p=dfs(dfs,(t-cnt+1)/cnt);
						for(auto&&e:p)e+=4;
						reverse(all(v));
						for(auto&&e:v)p.insert(p.begin(),e);
						reverse(all(v));
						return p;
					}
				}while(next_permutation(all(v)));
			}
			vector<int> p=dfs(dfs,t-1);
			p.insert(p.begin(),p.size());
			return p;
		}
	};

	vector<int> ans=dfs(dfs,k);

	return ans;
}

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