QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473076#8529. Balance of PermutationGenshinImpactsFault#TL 6926ms44588kbC++142.4kb2024-07-11 21:38:412024-07-11 21:38:42

Judging History

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

  • [2024-07-11 21:38:42]
  • 评测
  • 测评结果:TL
  • 用时:6926ms
  • 内存:44588kb
  • [2024-07-11 21:38:41]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
const int N = 35;
const int M = N * N / 2;
int n, b, mxb;
__int128 m;
bool used[N];
__int128 f[2][N * N][N][N];
int mu[N][N], ad[N][N];
int a[N], cur_cnt = 0, cur_b = 0;

void read(__int128 &x) {
	x = 0; char c = getchar();
	for(; c < '0' || c > '9'; c = getchar());
	for(; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + (c - '0');
}
void print(__int128 x) {
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
__int128 calc(int x, int cnt, int bb) {
	for(int i = 0; i < 2; i++)
		for(int j = M - mxb; j <= M + mxb; j++)
			for(int k = 0; k <= n + 1; k++)
				for(int h = 0; h <= n + 1; h++)
					f[i][j][k][h] = 0;
	f[x & 1][M + bb][cnt][0] = 1;
	for(int i = x + 1; i <= n; i++) {
		int cur = i & 1;
		int pre = cur ^ 1;
		for(int j = M - mxb; j <= M + mxb; j++)
			for(int k = 0; k <= n; k++)
				for(int h = 0; h <= n; h++) {
					f[cur][j][k][h] = 0;
				}
		for(int j = M - mxb; j <= M + mxb; j++)
			for(int k = 0; k <= n; k++)
				for(int h = 0; h <= n; h++) {
					if(!f[pre][j][k][h]) continue;
					if(!used[i]) {
						f[cur][j][k][h] += ad[k][h] * f[pre][j][k][h];
						f[cur][j - 2 * i][k + 1][h + 1] += f[pre][j][k][h];
						if(k && h) f[cur][j + 2 * i][k - 1][h - 1] += mu[k][h] * f[pre][j][k][h];
					}
					else {
						f[cur][j][k][h + 1] += f[pre][j][k][h];
						if(k) f[cur][j + 2 * i][k - 1][h] += k * f[pre][j][k][h];
					}
				}
	}
	return f[n & 1][M + b][0][0];
}
int main() {
	// int cur = clock();
	cin >> n >> b; read(m);
	for(int i = 1; i <= n; i++) mxb += abs(n - i + 1 - i);
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			mu[i][j] = i * j, ad[i][j] = 1 + i + j;
	// mxb = n * n;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(used[j]) continue;
			used[j] = 1, a[i] = j;
			int nxt_cnt = 0;
			for(int k = 1; k <= i; k++) if(!used[k]) ++nxt_cnt;
			int nxt_b = cur_b;
			if(j > i) nxt_b += -i;
			if(j < i) nxt_b += i;
			bool flag = 0;
			for(int k = 1; k < i; k++) {
				if(a[k] == i) flag = 1;
			}
			if(flag) nxt_b += i;
			else if(a[i] != i) nxt_b -= i;
			__int128 rem = calc(i, nxt_cnt, nxt_b);
			if(rem >= m) {
				cur_cnt = nxt_cnt, cur_b = nxt_b;
				break;
			}
			else {
				used[j] = 0;
				m -= rem;
			}
		}
	}
	for(int i = 1; i <= n; i++) cout << a[i] << " ";
	cout << "\n";
	// cout << clock() - cur << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6 6 6

output:

1 2 6 3 4 5 

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 6665ms
memory: 44588kb

input:

30 300 3030303030303030303030

output:

1 2 3 4 9 23 20 28 24 16 21 17 27 29 8 26 25 30 19 18 22 12 7 13 6 10 5 15 14 11 

result:

ok 30 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 7736kb

input:

1 0 1

output:

1 

result:

ok 1 number(s): "1"

Test #4:

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

input:

2 0 1

output:

1 2 

result:

ok 2 number(s): "1 2"

Test #5:

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

input:

2 2 1

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #6:

score: 0
Accepted
time: 1ms
memory: 7740kb

input:

5 8 3

output:

1 5 4 2 3 

result:

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

Test #7:

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

input:

7 20 100

output:

3 6 7 4 1 5 2 

result:

ok 7 numbers

Test #8:

score: 0
Accepted
time: 1ms
memory: 9788kb

input:

7 2 6

output:

2 1 3 4 5 6 7 

result:

ok 7 numbers

Test #9:

score: 0
Accepted
time: 2ms
memory: 9760kb

input:

7 24 1

output:

4 5 6 7 1 2 3 

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 9856kb

input:

7 22 360

output:

7 6 4 3 5 2 1 

result:

ok 7 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 9768kb

input:

7 20 358

output:

5 7 2 4 6 3 1 

result:

ok 7 numbers

Test #12:

score: 0
Accepted
time: 8ms
memory: 11900kb

input:

10 48 10001

output:

7 5 8 9 6 10 3 4 1 2 

result:

ok 10 numbers

Test #13:

score: 0
Accepted
time: 7ms
memory: 11804kb

input:

10 42 10101

output:

3 9 6 8 10 5 7 2 1 4 

result:

ok 10 numbers

Test #14:

score: 0
Accepted
time: 2643ms
memory: 32316kb

input:

25 300 1

output:

7 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 8 9 10 11 12 13 

result:

ok 25 numbers

Test #15:

score: 0
Accepted
time: 4524ms
memory: 34352kb

input:

25 300 283788388040048639877

output:

25 24 23 22 21 20 19 18 17 16 11 12 13 14 15 10 9 8 7 5 6 4 2 1 3 

result:

ok 25 numbers

Test #16:

score: 0
Accepted
time: 4640ms
memory: 36324kb

input:

26 302 105773752969551707419545

output:

19 22 25 13 17 18 23 20 10 26 16 6 5 11 14 12 24 4 3 21 1 15 7 8 2 9 

result:

ok 26 numbers

Test #17:

score: 0
Accepted
time: 4907ms
memory: 38488kb

input:

27 308 8781128321749037280676555

output:

16 18 17 21 25 6 20 24 22 15 27 5 7 8 2 9 26 13 1 3 14 10 23 19 4 11 12 

result:

ok 27 numbers

Test #18:

score: 0
Accepted
time: 5306ms
memory: 40440kb

input:

28 304 806517199954337651602356955

output:

12 17 5 16 23 26 25 15 20 2 19 7 22 24 6 13 11 10 28 8 1 21 18 14 27 3 4 9 

result:

ok 28 numbers

Test #19:

score: 0
Accepted
time: 6926ms
memory: 42540kb

input:

29 322 40281026669581503094652149519

output:

16 21 10 25 17 29 9 28 2 8 26 27 22 4 3 5 18 14 19 1 23 20 15 11 13 7 6 12 24 

result:

ok 29 numbers

Test #20:

score: -100
Time Limit Exceeded

input:

30 400 46479902466857426153849991132

output:


result: