oj.uz

답안 #602983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602983 2022-07-23T13:39:23 Z tutis 순열 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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