Submission #1154778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154778		Sharky	Permutation (APIO22_perm)	C++17	0 / 100	0 ms	324 KiB

perm

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

void append(vector<int>& v, int x, bool bk = 1) {
	map<int, int> e;
	for (int& a : v) {
		if (a > x) a++;
		e[a]++;
	}
	for (int i = 0;; i++) if (!e.count(i)) {
		if (bk) v.push_back(i);
		else v.insert(v.begin(), i);
		break;
	}
}

const int big = 100000;
const int small = -1;

std::vector<int> construct_permutation(long long k) {
	vector<int> ops;
	while (k) {
		ops.push_back(k % 4);
		k /= 4;
	}
	reverse(ops.begin(), ops.end());
	vector<int> p;
	for (int i : ops) {
		if (p.empty()) {
			if (i == 1) p = {};
			else if (i == 2) p = {0};
			else if (i == 3) p = {1, 0};
		} else {
			int n = p.size();
			if (i == 0) {
				append(p, big);
				append(p, big);
			} else if (i == 1) {
				append(p, big);
				append(p, big);
				append(p, small);
			} else if (i == 2) {
				append(p, big);
				append(p, small);
				append(p, big);
			} else if (i == 3) {
				int p0 = -1, p1 = -1;
				for (int j = 0; j < n; j++) if (p[j] == 0) {
					p0 = j;
					break;
				}
				for (int j = 0; j < n; j++) if (p[j] == 1) {
					p1 = j;
					break;
				}
				bool ok = (p0 != -1 && p1 != -1 && p1 < p0);
				if (ok) {
					append(p, big);
					append(p, big);
					append(p, 1);
				} else {
					append(p, big);
					append(p, small);
					append(p, big);
					append(p, small);
				}
			}
		}
	}
	return p;
}

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