Submission #671067

#	Time	Username	Problem	Language	Result	Execution time	Memory
671067		arnold518	Permutation (APIO22_perm)	C++17	100 / 100	132 ms	19620 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9+7;
 
ll K;
 
unordered_map<ll, int> M;
int f(ll x)
{
	if(x==1) return 0;
	if(x==0) return INF;
	if(M.find(x)!=M.end()) return M[x];
	int ret=INF;
	for(int i=2; i<=7; i++)
	{
		if(i==4 || i==5 || i==6) continue;
		ret=min((ll)ret, f(x/i)+i+x%i-1);
	}
	return M[x]=ret;
}
 
void restore(ll x, vector<pii> &V)
{
	if(x==1) return;
	for(int i=2; i<=7; i++)
	{
		if(i==4 || i==5 || i==6) continue;
		if(f(x/i)+i+x%i-1==f(x))
		{
			restore(x/i, V);
			V.push_back({i-1, x%i});
			return;
		}
	}
}
 
std::vector<int> construct_permutation(long long _k)
{
	K=_k;
	vector<int> ans;
	vector<pii> V;
 
	restore(K, V);
	int cnt=0, cnt2=0;
	for(auto it : V)
	{
		for(int i=0; i<it.second; i++) cnt++, cnt2++;
	}
 
	for(auto it : V)
	{
		cnt+=it.first;
		for(int i=1; i<=it.first; i++) ans.push_back(cnt-i);
		for(int i=1; i<=it.second; i++) ans.push_back(--cnt2);
	}
	
	return ans;
}

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