Submission #821436

#	Time	Username	Problem	Language	Result	Execution time	Memory
821436		radaiosm7	Permutation (APIO22_perm)	C++17	71.22 / 100	10 ms	1364 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;
	int cc;
	
	for (int i=59; i >= 1; --i) {
		cc = 0;

		while (k >= po[i]) {
			k -= po[i];
			++cc;
			++k;
		}

		if (cc == 1) {
			groups.push_back(i);
			sum += i;
		}

		else if (cc == 2) {
			groups.push_back(i+1);
			sum += i+1;
			--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: 61.215384618 / 90