oj.uz

Submission #725019

# Submission time Handle Problem Language Result Execution time Memory
725019 2023-04-16T13:00:21 Z hollwo_pelw Permutation (APIO22_perm) C++17
100 / 100
 2 ms 352 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 352 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct