QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #707405 | #9463. 基础 ABC 练习题 | Aaronwrq | 0 | 2411ms | 7928kb | C++14 | 2.1kb | 2024-11-03 15:51:58 | 2024-11-03 15:51:59 |
Judging History
answer
#include <bits/stdc++.h>
#define MAXN 65
using namespace std;
using uint = unsigned int;
int T, cid, n;
bool S1[MAXN], S2[MAXN];
string S;
uint dp[MAXN][MAXN][MAXN][2][2], ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> T >> cid;
for (int tid = 1; tid <= T; ++tid) {
cin >> n;
for (int i = 0; i <= n; ++i) {
char ch; cin >> ch;
S1[i] = ch - '0';
}
for (int i = 0; i <= n; ++i) {
char ch; cin >> ch;
S2[i] = ch - '0';
}
cin >> S;
if (n != 60) {cout << "-1\n"; continue;}
ans = 0;
for (int A = 0; A <= n; ++A) for (int B = 0; A + B <= n; ++B) {
int C = n - A - B;
int minabc = A, minbca = B;
while (minabc <= n && !S1[minabc]) ++minabc;
while (minbca <= n && !S2[minbca]) ++minbca;
if (minabc + minbca > n) continue;
C = min(C, n - minabc - minbca);
memset(dp, 0, sizeof(dp));
dp[0][0][0][A == 0][B == 0] = 1;
for (int a = 0; a <= n; ++a) for (int b = 0; b <= n; ++b) for (int c = 0; c <= n; ++c) {
int all = a + b + c;
if (a < n && (S[all] == 'A' || S[all] == '?')) {
int nowA = a - c + 1;
if (nowA <= A) {
dp[a + 1][b][c][nowA == A][0] += dp[a][b][c][0][0];
dp[a + 1][b][c][nowA == A][1] += dp[a][b][c][0][1];
dp[a + 1][b][c][1][0] += dp[a][b][c][1][0];
dp[a + 1][b][c][1][1] += dp[a][b][c][1][1];
}
}
if (b < n && (S[all] == 'B' || S[all] == '?')) {
int nowB = b - a + 1;
if (nowB <= B) {
dp[a][b + 1][c][0][nowB == B] += dp[a][b][c][0][0];
dp[a][b + 1][c][0][1] += dp[a][b][c][0][1];
dp[a][b + 1][c][1][nowB == B] += dp[a][b][c][1][0];
dp[a][b + 1][c][1][1] += dp[a][b][c][1][1];
}
}
if (c < n && (S[all] == 'C' || S[all] == '?')) {
int nowC = c - b + 1;
if (nowC <= C) {
dp[a][b][c + 1][0][0] += dp[a][b][c][0][0];
dp[a][b][c + 1][0][1] += dp[a][b][c][0][1];
dp[a][b][c + 1][1][0] += dp[a][b][c][1][0];
dp[a][b][c + 1][1][1] += dp[a][b][c][1][1];
}
}
ans += dp[n][n][n][1][1];
}
}
cout << ans << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1604ms
memory: 7844kb
input:
60 1 1 11 11 ABC 2 111 111 CABABC 3 1111 1111 CAABBCBAC 4 11111 11111 BACBBACBACAC 5 111111 111111 CABCCBBAABCCBAA 6 1111111 1111111 ABABABCACBCBCCACBA 7 11111111 11111111 BCAABACBBCBBABCCAACAC 8 111111111 111111111 CCBCBBBCAABCBCAAAAACBCBA 9 1111111111 1111111111 CCCCACABCBABAABCCAABABBCBBA 10 1111...
output:
-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 -1 -1 -1 -1 -1 -1 -1 -1 -1 62
result:
wrong answer Your answer is wrong in testcase 60
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 2411ms
memory: 7928kb
input:
60 3 1 11 11 ??? 2 111 111 ?????? 3 1111 1111 ????????? 4 11111 11111 ???????????? 5 111111 111111 ??????????????? 6 1111111 1111111 ?????????????????? 7 11111111 11111111 ????????????????????? 8 111111111 111111111 ???????????????????????? 9 1111111111 1111111111 ??????????????????????????? 10 1111...
output:
-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 -1 -1 -1 -1 -1 -1 -1 -1 -1 506879488
result:
wrong answer Your answer is wrong in testcase 60
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%