QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371824#7778. Turning Permutationcomeintocalm#WA 1ms3904kbC++171.9kb2024-03-30 16:51:482024-03-30 16:51:48

Judging History

你现在查看的是最新测评结果

  • [2024-03-30 16:51:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3904kb
  • [2024-03-30 16:51:48]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
#define LI __int128
using namespace std;

const int MAXN = 55;
const LI inf = 1e18 + 1;
int n;
LL K;
LI f[MAXN][2][2], c[MAXN][MAXN];

#define inc(t1) ( (t1) = min ((t1), inf) )

int a[MAXN];
LI calc() {
	LI ret = 1;
	int cnt = 0;
	for (int p = 1, q; p <= n; p = q + 1) {
		q = p;
		while (q <= n && a[q]) ++q;
		ret *= f[q - p][p != 1][q != n + 1];
		//cout << q - p << " " << (LL) f[q - p][p != 1][q != n + 1] << endl;
		inc (ret);
		cnt += q - p;
		ret *= c[cnt][q - p];
		inc (ret);
	}
	return ret;
}

int ans[MAXN];
void dfs (int dep, LI V) {
	//cout << dep << endl;
	if (dep == n && V == 1) {
		for (int i = 1; i <= n; ++i)
			if (a[i]) ans[n] = i;
		for (int i = 1; i <= n; ++i)
			printf ("%d ", ans[i]);
		exit (0);
	}
	for (int i = 1; i <= n; ++i)
		if (a[i]) {
			//cout << i << " ";
			a[i] = 0;
			LI ret = calc();
			//cout << (LL) ret << endl;
			if (ret >= V) {
				ans[dep] = i;
				dfs (dep + 1, V);
				return ;
			}
			else V -= ret;
			a[i] = 1;
		}
}

int main() {
	int i,j,k;
	scanf ("%d%lld", &n, &K);
	for (i = 1; i <= n; ++i) a[i] = 1;
	//a[1] = 0;
	//calc();
	//return 0;
	for (i = 1, c[0][0] = 1; i <= n; ++i)
		for (j = 1, c[i][0] = 1; j <= i; ++j) {
			c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
			inc(c[i][j]);
		}
	f[0][0][0] = f[0][1][0] = f[0][0][1] = f[0][1][1] = 1;
	f[1][0][0] = f[1][1][0] = f[1][0][1] = f[1][1][1] = 1;
	for (i = 2; i <= n; ++i)
		for (int p = 0; p < 2; ++p)
			for (int q = 0; q < 2; ++q)
				for (k = 1; k <= i; ++k) {
					if (p == 1 && k == 1) continue ;
					if (q == 1 && k == i) continue ;
					LI ret = 1;
					ret = f[k - 1][p][1] * f[i - k][1][q];
					inc (ret);
					f[i][p][q] += ret * c[i - 1][k - 1];
					inc (f[i][p][q]);
				}
	//a[2] = 0;
	//cout << (LL) calc();
	//return 0;
	//cout << (LL) f[2][1][0] << endl;
	dfs (1, K);
	puts ("-1");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3880kb

input:

3 2

output:

2 1 3 

result:

ok 3 number(s): "2 1 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

3 5

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

4 6

output:

3 1 2 4 

result:

ok 4 number(s): "3 1 2 4"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4 11

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3748kb

input:

3 1

output:

1 2 3 

result:

wrong answer 2nd numbers differ - expected: '3', found: '2'