QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #854261 | #9995. 乒乓球赛 | samnever | WA | 24ms | 5904kb | C++23 | 4.4kb | 2025-01-11 23:08:35 | 2025-01-11 23:08:36 |
Judging History
answer
#include<cstdio>
#include<ctime>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<random>
#include<numeric>
#include<functional>
#define fs(i,x,y) for(int i=(x),_=(y);i<=_;++i)
#define fn(i,x,y) for(int i=(x),_=(y);i>=_;--i)
#define tor(i,v,x) for(int i=head[x],v=to[i];i;i=nxt[i],v=to[i])
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define mpi(x,y) make_pair(x,y)
#define pi pair<int,int>
#define fi first
#define se second
// #define int ll
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
template<typename T>
void read(T& x) {
x = 0; char ch = getchar(); bool f = 0;
while (ch < '0' || ch > '9') {
if (ch == '-')f = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
x = f ? -x : x;
}
template<typename T, typename...Args>
void read(T& x, Args &...args) {
read(x); read(args...);
}
const int N = 1e6 + 7, P = 998244353;
int n, m;
int a[N], b[N];
int dp[23][23];
bool ban[23][23];
bool bala = false;
void solve() {
// if (bala)cout << "///" << endl;
read(n);
bool ok = true;
fs(i, 1, n) {
read(a[i], b[i]);
if (a[i] == -1)continue;
if (a[i] + b[i] != i)ok = false;
if (i < n) {
if (i <= 20) {
if (max(a[i], b[i]) >= 11)ok = false;
} else {
if (abs(a[i] - b[i]) >= 2)ok = false;
}
} else {
if (i <= 20) {
if (max(a[i], b[i]) != 11)ok = false;
} else {
if (abs(a[i] - b[i]) != 2)ok = false;
}
}
}
// if (bala) {
// cout << n << endl;
// fs(i, 1, n)cout << a[i] << ' ' << b[i] << endl;
// }
if (!ok) {
printf("0\n");
return;
}
fs(i, 0, 20)fs(j, 0, 20)ban[i][j] = false, dp[i][j] = 0;
// if (bala) {
// fs(i, 0, 10) {
// fs(j, 0, 10)cout << ban[i][j] << ' ';
// cout << endl;
// }
// cout << endl;
// }
fs(i, 1, n) {
if (a[i] >= 0) {
fs(j, 0, i)ban[j][i - j] = true;
// if (bala) {
// fs(i, 0, 10) {
// fs(j, 0, 10)cout << ban[i][j] << ' ';
// cout << endl;
// }
// cout << i << endl << endl;
// }
ban[a[i]][b[i]] = ban[b[i]][a[i]] = false;
}
}
dp[0][0] = 1;
ban[0][0] = true;
fs(i, 0, 10) {
fs(j, 0, 10) {
if (ban[i][j])continue;
if (j > 0)dp[i][j] = (dp[i][j] + dp[i][j - 1]) % P;
if (i > 0)dp[i][j] = (dp[i][j] + dp[i - 1][j]) % P;
}
// if (bala) {
// fs(i, 0, 10) {
// fs(j, 0, 10)cout << ban[i][j] << ' ';
// cout << endl;
// }
// }
}
// if (bala) {
// fs(i, 0, 10) {
// fs(j, 0, 10)cout << dp[i][j] << ' ';
// cout << endl;
// }
// }
if (n > 20) {
if (n % 2) {
printf("0\n");
} else {
int ans = dp[10][10];
fs(i, 21, n - 1) {
if ((i % 2))ans = ans * 2 % P;
}
printf("%d\n", ans);
}
} else {
if (n < 11) {
printf("0\n");
} else {
printf("%d\n", (dp[10][n - 11] + dp[n - 11][10]) % P);
}
}
}
signed main() {
// freopen("6.in", "r", stdin);
// freopen("6.out", "w", stdout);
int T;
read(T);
fs(i, 1, T) {
if (i == 19434)bala = true;
solve();
if (i == 19434)bala = false;
}
return 0;
}
/*
17
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
4 7
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
*/
/*
1 1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10 0
1 3 6 10 15 21 28 36 45 0 0
1 4 10 20 35 56 84 120 0 0 0
1 5 15 35 70 126 210 330 330 330 330
1 6 21 56 126 252 0 330 660 990 1320
1 7 28 84 210 0 0 330 990 1980 3300
1 8 36 120 330 330 330 660 1650 3630 6930
1 9 45 0 330 660 990 1650 3300 6930 0
1 10 0 0 330 990 1980 3630 6930 0 0
1 0 0 0 330 1320 3300 6930 0 0 0
6600
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5780kb
input:
7 11 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 11 22 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
2 0 0 0 369512 0 864
result:
ok 7 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
12 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11 0 -1 -1 12 -1 -1 -1 -1 -...
output:
0 2 22 0 0 0 0 369512 0 0 0 0
result:
ok 12 lines
Test #3:
score: 0
Accepted
time: 24ms
memory: 5904kb
input:
20000 16 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 13 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
6006 0 0 132 0 0 2002 0 0 0 0 369512 184756 0 0 0 0 41756 572 0 2 2002 2 0 6006 0 0 38896 369512 87516 369512 0 6006 0 0 6006 0 369512 0 0 369512 572 184756 0 739024 87516 145860 2 0 16016 0 2002 6006 0 0 0 0 0 132 6006 572 2002 0 3520 0 0 0 0 22 0 2 184756 0 0 0 0 0 0 0 0 0 572 3432 572 132 3960 57...
result:
ok 20000 lines
Test #4:
score: -100
Wrong Answer
time: 24ms
memory: 5784kb
input:
20000 25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 6 14 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 4 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
0 0 0 0 2002 0 1350 87516 87516 0 132 132 0 0 38896 0 31680 0 572 132 0 184756 38896 42 38896 184756 572 6006 38896 369512 0 0 0 252 0 0 0 739024 87516 0 0 0 132 0 0 132 132 22 0 132 0 87516 0 0 0 739024 132 16016 0 0 0 0 0 22 0 22 0 0 0 2002 0 2002 0 369512 22 22 38896 38896 87516 0 0 0 0 0 0 2 252...
result:
wrong answer 675th lines differ - expected: '739024', found: '350064'