oj.uz

Submission #602959

# Submission time Handle Problem Language Result Execution time Memory
602959 2022-07-23T13:25:39 Z tutis Permutation (APIO22_perm) C++17
93 / 100
 28 ms 348 KB 
#include "perm.h"
using namespace std;
#include <iostream>
#include <random>
using ll = long long;
mt19937_64 rng(0);
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 (rng() % 5 == 0 && i != 0 && sum != k)
				continue;
			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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
82.999999998 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 212 KB Output is correct
5 Partially correct 11 ms 320 KB Partially correct
6 Correct 8 ms 304 KB Output is correct
7 Correct 17 ms 344 KB Output is correct
8 Partially correct 28 ms 328 KB Partially correct
9 Partially correct 23 ms 348 KB Partially correct
10 Partially correct 25 ms 332 KB Partially correct
11 Partially correct 23 ms 324 KB Partially correct
12 Partially correct 18 ms 328 KB Partially correct
13 Partially correct 24 ms 320 KB Partially correct