제출 #671060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671060		arnold518	순열 (APIO22_perm)	C++17	94.67 / 100	16 ms	3232 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<=4; i++)
	{
		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<=4; i++)
	{
		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: 84.666666663 / 90