Submission #724934

#	Time	Username	Problem	Language	Result	Execution time	Memory
724934		hollwo_pelw	Permutation (APIO22_perm)	C++17	0 / 100	1 ms	212 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};

	auto p = construct_permutation(k / 4);

	int n = p.size();

	if (k % 4 == 0) {
		p.push_back(n);
		p.push_back(n + 1);
	} else if (k % 4 == 1) {
		p.push_back(n);
		p.push_back(n + 1);
		p.push_back(-1);
	} else if (k % 4 == 2) {
		p.push_back(n);
		p.push_back(-1);
		p.push_back(n + 1);
	} else {
		p.insert(p.begin(), -1);
		p.insert(p.begin(), n);
		p.push_back(n + 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: 0 / 10
• Subtask 2: 0 / 90