Submission #742012

#	Time	Username	Problem	Language	Result	Execution time	Memory
742012		t6twotwo	Permutation (APIO22_perm)	C++17	95 / 100	2 ms	340 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> B2(ll k) {
	int p = 63 - __builtin_clzll(k);
	int v = __builtin_popcountll(k) - 1;
	int u = v;
	vector<int> ans;
	for (int i = p - 1; i >= 0; i--) {
		ans.push_back(u++);
		if (k >> i & 1) {
			ans.push_back(--v);
		}
	}
	return ans;
}
vector<int> construct_permutation(ll k) {
	vector<ll> pw(38);
	pw[0] = 1;
	for (int i = 1; i < 38; i++) {
		pw[i] = pw[i - 1] * 3;
	}
	int p = -1, cnt = 0;
	for (int i = 0; i < 38; i++) {
		if (k / pw[i] % 3) {
			p = i;
			cnt++;
		}
	}
	int v = cnt - 1;
	int u = v;
	vector<int> ans;
	if (k / pw[p] % 3 == 2) {
		ans.push_back(u++);
	}
	for (int i = p - 1; i >= 0; i--) {
		if (k / pw[i] % 3 == 0) {
			ans.push_back(u + 1);
			ans.push_back(u);
			u += 2;
		} else if (k / pw[i] % 3 == 1) {
			ans.push_back(u + 1);
			ans.push_back(u);
			ans.push_back(--v);
			u += 2;
		} else {
			ans.push_back(u + 1);
			ans.push_back(--v);
			ans.push_back(u);
			u += 2;
		}
	}
	auto a = B2(k);
	if (a.size() < ans.size()) {
		ans = a;
	}
	return ans;
}

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