Submission #777090

#	Time	Username	Problem	Language	Result	Execution time	Memory
777090		Alan	Permutation (APIO22_perm)	C++17	93.67 / 100	2 ms	340 KiB

perm

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

vector<int> solve1 (ll k) {
	vector<int> ans, bin;
	int l = 0, r = 120;
	for (int i = 0; i < 60; i++) bin.push_back(!!((1LL<<i) & k));
	while (!bin.back()) bin.pop_back();
	int sz = bin.size();
	for (int i = 0; i+1 < sz; i++) {
		if (bin[i]) ans.push_back(r--);
		ans.push_back(l++);
	}
	for (auto& x : ans) if (x >= l) x = x - (r-l+1);
	return ans;
}  

vector<int> solve2 (ll k) {
	if (k <= 6) return {};
	vector<int> res = {1, 0, 2};
	ll cur = 6;
	while (cur*2 < k) {
		cur *= 2;
		res.push_back(res.back()+1);
	}
	k -= cur;
	for (int x = res.back(); x > 0; x--, cur /= 2) if (k >= cur) {
		for (auto& y : res) if (y > x) y++;
		k -= cur;
		res.push_back(x+1);
	}
	if (k >= 2) {
		for (auto& y : res) if (y >= 1) y++;
		res.push_back(1);
		k = 0;
	}
	if (k >= 1) {
		for (auto& y : res) if (y >= 0) y++;
		res.push_back(0);
	}
	return res;
}

vector<int> construct_permutation(ll k) {
	vector<int> ans = solve1(k), ans2 = solve2(k);
	if (!ans2.empty() && ans.size() > ans2.size()) swap(ans, ans2);
	return ans;
}

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