oj.uz

Submission #602980

# Submission time Handle Problem Language Result Execution time Memory
602980 2022-07-23T13:38:22 Z tutis Permutation (APIO22_perm) C++17
91.6667 / 100
 278 ms 488 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(6);
		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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
81.666666666 / 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 10 ms 212 KB Output is correct
4 Correct 24 ms 320 KB Output is correct
5 Partially correct 124 ms 456 KB Partially correct
6 Correct 72 ms 332 KB Output is correct
7 Correct 122 ms 468 KB Output is correct
8 Partially correct 184 ms 332 KB Partially correct
9 Correct 34 ms 356 KB Output is correct
10 Partially correct 278 ms 488 KB Partially correct
11 Partially correct 171 ms 344 KB Partially correct
12 Partially correct 151 ms 356 KB Partially correct
13 Partially correct 225 ms 360 KB Partially correct