Submission #725019

#	Time	Username	Problem	Language	Result	Execution time	Memory
725019		hollwo_pelw	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	352 KiB

perm

#include "perm.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

vector<int> construct_permutation(long long k) {
	if (k == 1) return {};
	if (k == 2) return {0};
	if (k == 3) return {1, 0};

	vector<int> bits;
	for (; k; k /= 4)
		bits.push_back(k % 4);

	bool have3 = 0;
	int used_for_3 = 0;
	vector<int> p;

	if (bits.back() == 1) {
		p = {};
	} else if (bits.back() == 2) {
		p = {0};
	} else { // == 3
		have3 = 1;
		p.push_back(-1e9);
		p.push_back(-1e9-1);
	}

	bits.pop_back();
	reverse(bits.begin(), bits.end());

	for (int f : bits) {
		// cout << f << '\n';
		if (f == 0) {
			p.push_back(p.size());
			p.push_back(p.size());
		} else if (f == 1) {
			p.push_back(p.size());
			p.push_back(p.size());
			p.insert(p.begin(), p.size());
		} else if (f == 2) {
			p.push_back(p.size());
			p.insert(p.begin(), p.size());
			p.push_back(p.size());
		} else {
			if (have3) {
				p.push_back(p.size());
				p.push_back(p.size());
				p.push_back(-- used_for_3);
			} else {
				p.push_back(p.size());
				p.push_back(-1e9);
				p.push_back(p.size());
				p.push_back(-1e9 - 1);
				have3 = 1;
			}
		}
	}

	auto q = p;
	sort(q.begin(), q.end());

	for (int &v : p)
		v = lower_bound(q.begin(), q.end(), v) - q.begin();

	return p;
}

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