oj.uz

Submission #602978

# Submission time Handle Problem Language Result Execution time Memory
602978 2022-07-23T13:38:03 Z tutis Permutation (APIO22_perm) C++17
91.3333 / 100
 61 ms 472 KB 
#include "perm.h"
using namespace std;
#include <iostream>
#include <random>
#include <functional>
using ll = long long;
std::vector<int> construct_permutation(long long k)
{
	vector<int>ret = { -1};
	vector<ll>dp = {1};
	k--;
	while (k != 0)
	{
		vector<int>ret_ = ret;
		vector<ll>dp_ = dp;
		ll k_ = k;
		function<void(int)>dfs = [&](int l)
		{
			if (k < k_ || (k == k_ && dp.size() < dp_.size()))
			{
				k_ = k;
				dp_ = dp;
				ret_ = ret;
			}
			if (l == 0)
				return;
			int sz = (int)ret.size();
			int gal = 0;
			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)
				{
					gal++;
					if (gal >= 3)
						break;
					k -= sum;
					dp.push_back(sum);
					for (int &j : ret)
						if (j >= i)
							j++;
					ret.push_back(i);

					dfs(l - 1);


					k += sum;
					dp.pop_back();
					ret.pop_back();
					for (int &j : ret)
						if (j >= i)
							j--;
				}
			}
		};
		dfs(3);
		ret = ret_;
		dp = dp_;
		k = k_;
	}
	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
81.333333333 / 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 3 ms 212 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Partially correct 30 ms 368 KB Partially correct
6 Correct 17 ms 316 KB Output is correct
7 Correct 27 ms 340 KB Output is correct
8 Partially correct 45 ms 472 KB Partially correct
9 Correct 10 ms 348 KB Output is correct
10 Partially correct 61 ms 376 KB Partially correct
11 Partially correct 39 ms 340 KB Partially correct
12 Partially correct 35 ms 364 KB Partially correct
13 Partially correct 52 ms 356 KB Partially correct