Submission #602995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602995	2022-07-23T13:59:41 Z	tutis	Permutation (APIO22_perm)	C++17	91.3333 / 100	26 ms	344 KB

perm

#include "perm.h"
using namespace std;
#include <iostream>
#include <random>
#include <functional>
#include <map>
using ll = long long;
map<ll, vector<int>>M;
std::vector<int> construct_permutation(long long k)
{
	if (k % 2 == 0)
	{
		vector<int>a = construct_permutation(k / 2);
		a.push_back((int)a.size());
		return a;
	}
	vector<int>ret = { -1};
	vector<ll>dp = {1};
	k--;
	while (k != 0)
	{
		int sz = (int)ret.size();
		for (int i = sz - 1; i >= 0; i--)
		{
			ll sum = 0;
			for (int j = 0; j < (int)ret.size(); j++)
				if (ret[j] < i)
					sum += dp[j];
			if (sum <= k)
			{
				k -= sum;
				dp.push_back(sum);
				for (int &j : ret)
					if (j >= i)
						j++;
				ret.push_back(i);
				break;
			}
		}
	}
	ret.erase(ret.begin());
	return M[k] = ret;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

81.333333333 / 90.0

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