Submission #821291

#	Time	Username	Problem	Language	Result	Execution time	Memory
821291		radaiosm7	Permutation (APIO22_perm)	C++17	64.62 / 100	10 ms	1324 KiB

perm

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

vector<int> construct_permutation(long long k) {
	--k;
	vector<int> groups;
	int sum = 0;
	vector<int> ans;
	long long po[61];
	po[0] = 1LL;
	for (int i=1; i <= 59; ++i) po[i] = po[i-1]*2LL;
	
	for (int i=59; i >= 2; --i) {
		if (k >= po[i]) {
			k -= po[i];
			groups.push_back(i);
			sum += i;
			++k;
		}
	}

	while (k > 0LL) {
		groups.push_back(1);
		--k;
		++sum;
	}

	--sum;
	int n = (int)groups.size();

	for (int i=0; i < n; ++i) {
		int from = sum-groups[i]+1;
		for (int j=from; j <= sum; ++j) ans.push_back(j);
		sum = from-1;
	}

	return ans;
}

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