oj.uz

답안 #602996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602996 2022-07-23T14:02:04 Z tutis 순열 (APIO22_perm) C++17
91.3333 / 100
 2 ms 340 KB 
#include "perm.h"
using namespace std;
#include <iostream>
#include <random>
#include <functional>
#include <map>
using ll = long long;
std::vector<int> construct_permutation(long long k)
{
	if (k % 2 == 0)
	{
		vector<int>a = construct_permutation(k / 2);
		a.push_back((int)a.size());
		return a;
	}
	if (k % 2 == 1 && k > 1000)
	{
		vector<int>a = construct_permutation(k - 1);
		a.insert(a.begin(), (int)a.size());
		return a;
	}
	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 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
81.333333333 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 260 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Partially correct 1 ms 340 KB Partially correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Partially correct 2 ms 340 KB Partially correct
9 Correct 1 ms 340 KB Output is correct
10 Partially correct 2 ms 340 KB Partially correct
11 Partially correct 2 ms 340 KB Partially correct
12 Partially correct 1 ms 340 KB Partially correct
13 Partially correct 2 ms 340 KB Partially correct