Submission #1208660

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

perm

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void add_max(vector<int> &p) {
	int n = (int) p.size();
	p.push_back(n);
}

void add_min(vector<int> &p) {
	for (int &x : p)
		x++;
	p.push_back(0);
}

void add_third(vector<int> &p) {
	for (int &x : p)
		if (x > 1)
			x++;
	p.push_back(2);
}

bool condition(vector<int> &p) {
	if (p.size() < 2) return false;
	int pos1 = -1, pos0 = -1;
	for (int i = 0; i < (int) p.size(); i++)
		if (p[i] == 0) pos0 = i;
		else if (p[i] == 1) pos1 = i;
	return pos1 < pos0;
}

vector<int> construct_permutation(ll k) {
	int h = 0;
	while ((1ll << (h + 1)) <= k)
		h++;
	vector<int> p;
	for (int i = h - 2; i >= 0; i -= 2) {
		int val = (k >> i) & 3;
		if (val == 0) {
			add_max(p);
			add_max(p);
		} else if (val == 1) {
			add_max(p);
			add_max(p);
			add_min(p);
		} else if (val == 2) {
			add_max(p);
			add_min(p);
			add_max(p);
		} else if (val == 3) {
			if (condition(p)) {
				add_max(p);
				add_max(p);
				add_third(p);
			} else {
				add_max(p);
				add_min(p);
				add_max(p);
				add_min(p);
			}
		}
	}
	if (h % 2 != 0) {
		add_max(p);
		if (k & 1) add_min(p);
	}
	return p;
}

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