Submission #1235842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235842		dizzy_groovy	Permutation (APIO22_perm)	C++20	100 / 100	1 ms	328 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> ans(long long k, int n) {
	vector<int> ans(n);
	iota(ans.begin(), ans.end(), 0);
	do {
		int ind1, ind0;
		for (int i = 0; i < n; i++) {
			if (ans[i] == 0) ind0 = i;
			if (ans[i] == 1) ind1 = i;
		}
		if (ind1 > ind0) continue;
		vector<long long> lans(n, 0);
		long long su = 1;
		for (long long i = 0; i < n; i++) {
			lans[i] = 1;
			for (long long j = 0; j < i; j++) {
				if (ans[i] > ans[j]) lans[i] += lans[j];
			}
			su += lans[i];
		}
		if (su == k) {
			return ans;
		}
	} while (next_permutation(ans.begin(), ans.end()));
	return {-1};
}

std::vector<int> construct_permutation(long long k)
{
	if (k < 12) {

		/*vector<int> lans;
		for (int i = 1; i < k; i++) {
			lans.push_back(lans.size());
		}
		reverse(lans.begin(), lans.end());*/
		int i = 1;
		while (true) {
			auto tmp = ans(k, i);
			if (tmp[0] != -1) return tmp;
			i++;
		}
	}
	vector<int> lans = construct_permutation(k / 4);
	lans.push_back(lans.size());
	if (k % 4 == 2) {
		for (auto &i : lans) i++;
		lans.push_back(0);
	}
	lans.push_back(lans.size());
	if (k % 4 == 1) {
		for (auto &i : lans) i++;
		lans.push_back(0);
	}
	if (k % 4 == 3) {
		for (auto &i : lans) if (i > 1) i++;
		lans.push_back(2);
	}
	return lans;
	/*for (int i = 1; i < 90; i++) {
		auto tmp = ans(k, i);
		if (tmp[0] == -1) continue;
		return tmp;
	}*/
	/*vector<int> p;
	long long cur = 1;
	for (long long i = 0; (1ll << (i + 1)) <= k; i++) {
		cur *= 2;
		p.push_back(i);
	}
	long long n = p.size();
	while (k - cur > 0) {
		long long x = __lg(k - cur);
		for (auto &i : p) {
			if (i >= x) i++;
		}
		p.push_back(x);
		cur += (1ll << x);
	}
	return p;*/
}

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