Submission #602953

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602953	2022-07-23T13:16:57 Z	tutis	Permutation (APIO22_perm)	C++17	91.3333 / 100	21 ms	340 KB

perm

#include "perm.h"
using namespace std;
#include <iostream>
using ll = long long;
std::vector<int> construct_permutation(long long k)
{
	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 ret;
}

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

81.333333333 / 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	2 ms	300 KB	Output is correct
5	Partially correct	10 ms	340 KB	Partially correct
6	Correct	5 ms	340 KB	Output is correct
7	Correct	8 ms	340 KB	Output is correct
8	Partially correct	13 ms	332 KB	Partially correct
9	Correct	3 ms	340 KB	Output is correct
10	Partially correct	21 ms	336 KB	Partially correct
11	Partially correct	13 ms	340 KB	Partially correct
12	Partially correct	11 ms	324 KB	Partially correct
13	Partially correct	16 ms	328 KB	Partially correct