Submission #576823

#	Time	Username	Problem	Language	Result	Execution time	Memory
576823		dutinmeow	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	384 KiB

perm

#include "perm.h"

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

namespace permutation {
	vector<int> construct_permutation_slow(long long k) {
		vector<int> ret(k - 1);
		for (int i = 0; i < k - 1; i++)
			ret[i] = k - 2 - i;
		return ret;
	}
	
	const array<int, 5> primes = {2, 3, 5, 7, 11};

	vector<int> construct_permutation_dumb(long long k) {
		if (k <= 3)
			return construct_permutation_slow(k);
		for (int p : primes) {
			if (k % p != 0 || k == p)
				continue;
			auto ret = construct_permutation_dumb(k / p);
			auto tem = construct_permutation_dumb(p);
			int r = ret.size();
			for (int t : tem)
				ret.push_back(t + r);
			return ret;
		}
		auto ret = construct_permutation_dumb(k / 2);
		ret.push_back(ret.size());
		ret.insert(ret.begin(), ret.size());
		return ret;
	}
}

vector<int> construct_permutation(long long k) { 
	if (k <= 90)
		return permutation::construct_permutation_slow(k);
	else 
		return permutation::construct_permutation_dumb(k);
}

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