oj.uz

Submission #602983

# Submission time Handle Problem Language Result Execution time Memory
602983 2022-07-23T13:39:23 Z tutis Permutation (APIO22_perm) C++17
91.6667 / 100
 830 ms 620 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(8);
		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 2 ms 212 KB Output is correct

Subtask #2
81.666666666 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 29 ms 340 KB Output is correct
4 Correct 66 ms 312 KB Output is correct
5 Partially correct 377 ms 492 KB Partially correct
6 Correct 229 ms 316 KB Output is correct
7 Correct 360 ms 320 KB Output is correct
8 Partially correct 592 ms 372 KB Partially correct
9 Correct 154 ms 324 KB Output is correct
10 Partially correct 830 ms 316 KB Partially correct
11 Partially correct 569 ms 460 KB Partially correct
12 Partially correct 468 ms 472 KB Partially correct
13 Partially correct 666 ms 620 KB Partially correct