Submission #1065065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065065		sammyuri	Permutation (APIO22_perm)	C++17	100 / 100	6 ms	348 KiB

perm

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

vector<int> normalise(vector<int> xx, int fac = 2) {
	vector<int> values = xx;
	sort(values.begin(), values.end());
	vector<int> ans;
	for (auto a : xx) {
		auto it = lower_bound(values.begin(), values.end(), a);
		ans.push_back(fac * (it - values.begin()));
	}
	return ans;
}
const int BIG = 1000, SMALL = -1;

std::vector<int> construct_permutation(long long k) {
	// build initial permutation
	ll curpow = 2;
	vector<int> ans;
	vector<int> digits;
	while (k) {
		digits.push_back(k % 4);
		k /= 4;
	}
	if (digits.back() == 1)
		ans = {};
	else if (digits.back() == 2)
		ans = {0};
	else
		ans = {2, 0};
	digits.pop_back();
	reverse(digits.begin(), digits.end());
	for (auto digit : digits) {
		if (digit == 0) {
			ans.push_back(BIG); ans.push_back(BIG + 1);
		} else if (digit == 1) {
			ans.push_back(BIG); ans.push_back(BIG + 1); ans.push_back(SMALL);
		} else if (digit == 2) {
			ans.push_back(BIG); ans.push_back(SMALL); ans.push_back(BIG + 1);
		} else {
			bool seen1 = false, done = false;
			for (auto a : ans) {
				if (a == 0)
					if (seen1)
						done = true;
				if (a == 2)
					seen1 = true;
			}
			if (done) {
				ans.push_back(BIG); ans.push_back(BIG + 1); ans.push_back(3);
			} else {
				ans.push_back(BIG); ans.push_back(SMALL); ans.push_back(BIG + 1); ans.push_back(SMALL - 1);
			}
		}
		ans = normalise(ans);
	}
	ans = normalise(ans, 1);
	// for (auto a : ans)
	// 	cout << a << " "; cout << endl;
	return ans;
}

Compilation message (stderr)

perm.cpp: In function 'std::vector<int> construct_permutation(long long int)':
perm.cpp:20:5: warning: unused variable 'curpow' [-Wunused-variable]
   20 |  ll curpow = 2;
      |     ^~~~~~

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