QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#472934#8517. Interesting PathsGenshinImpactsFault#WA 0ms11804kbC++142.4kb2024-07-11 20:27:432024-07-11 20:27:44

Judging History

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

  • [2024-07-11 20:27:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:11804kb
  • [2024-07-11 20:27:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int n, b, mxb;
__int128 m;
bool used[N];
__int128 f[N][N * N * 2][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 = x; i <= n; i++)
		for(int j = N * N - mxb; j <= N * N + mxb; j++)
			for(int k = 0; k <= n + 1; k++)
				f[i][j][k] = 0;
	f[x][N * N + bb][cnt] = 1;
	int tmp = cnt;
	for(int i = x + 1; i <= n; i++)
		for(int j = N * N - mxb; j <= N * N + mxb; j++)
			for(int k = 0; k <= n; k++) {
				if(!used[i]) {
					f[i][j][k] += f[i - 1][j][k];
					if(k) f[i][j][k] += f[i - 1][j + 2 * i][k - 1];
					if(k) f[i][j][k] += k * f[i - 1][j][k];
					if(k + 1 > tmp) f[i][j][k] += (k - tmp + 1) * (k + 1) * f[i - 1][j - 2 * i][k + 1];
				}
				else {
					if(k) f[i][j][k] += f[i - 1][j][k - 1];
					f[i][j][k] += (k + 1) * f[i - 1][j - 2 * i][k + 1];
					--tmp;
				}
				// if(f[i][j][k] != 0) {
				// 	cout << ">>> " << i << " " << j - N * N << " " << k << " : ";
				// 	print(f[i][j][k]);
				// 	cout << "\n";
				// }
			}
	for(int i = 1; i <= n; i++) cout << a[i] << " ";
	cout << "\n";
	cout << "### " << x << " " << bb << " " << cnt << " : ";
	print(f[n][N * N + b][0]);
	cout << "\n";
	return f[n][N * N + b][0];
}
int main() {
	// ios::sync_with_stdio(0); cin.tie(nullptr);
	cin >> n >> b; read(m);
	for(int i = 1; i <= n; i++) mxb += abs(n - i + 1 - i);
	// 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";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 11804kb

input:

5 7
1 3
3 5
1 2
2 3
3 4
4 5
2 4

output:

1 0 0 0 0 
### 1 0 0 : 0
2 0 0 0 0 
### 1 -2 1 : 0
3 0 0 0 0 
### 1 -2 1 : 0
4 0 0 0 0 
### 1 -2 1 : 0
5 0 0 0 0 
### 1 -2 1 : 0
5 1 0 0 0 
### 2 0 1 : 0
5 2 0 0 0 
### 2 0 1 : 0
5 3 0 0 0 
### 2 -4 2 : 0
5 4 0 0 0 
### 2 -4 2 : 0
5 5 0 0 0 
### 2 -4 2 : 0
5 5 1 0 0 
### 3 0 2 : 0
5 5 2 0 0 
### 3 0...

result:

wrong answer 1st numbers differ - expected: '4', found: '1'