Submission #777090

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
777090	2023-07-08T16:08:57 Z	Alan	Permutation (APIO22_perm)	C++17	93.6667 / 100	2 ms	340 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct

Subtask #2

83.666666664 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Partially correct	1 ms	340 KB	Partially correct
6	Correct	1 ms	300 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Partially correct	2 ms	340 KB	Partially correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Partially correct	2 ms	340 KB	Partially correct
12	Partially correct	2 ms	304 KB	Partially correct
13	Partially correct	2 ms	340 KB	Partially correct