oj.uz

Submission #671067

# Submission time Handle Problem Language Result Execution time Memory
671067 2022-12-11T21:36:01 Z arnold518 Permutation (APIO22_perm) C++17
100 / 100
 132 ms 19620 KB 
#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.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
90.0 / 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 1 ms 340 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 20 ms 3440 KB Output is correct
6 Correct 21 ms 3588 KB Output is correct
7 Correct 53 ms 9792 KB Output is correct
8 Correct 132 ms 19620 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 95 ms 13668 KB Output is correct
12 Correct 83 ms 12260 KB Output is correct
13 Correct 80 ms 12000 KB Output is correct