QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #707427 | #9463. 基础 ABC 练习题 | Aaronwrq | 0 | 1425ms | 7996kb | C++14 | 1.7kb | 2024-11-03 15:56:52 | 2024-11-03 15:56:53 |
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;
void Add(uint &a, uint b) {a += b; return;}
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 != 40) {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;
for (bool v1 : {0, 1}) for (bool v2 : {0, 1}) {
if (a < n && (S[all] == 'A' || S[all] == '?')) {
int nowA = a - c + 1;
if (nowA <= A) Add(dp[a + 1][b][c][v1 || (nowA == A)][v2], dp[a][b][c][v1][v2]);
}
if (b < n && (S[all] == 'B' || S[all] == '?')) {
int nowB = b - a + 1;
if (nowB <= B) Add(dp[a][b + 1][c][v1][v2 || (nowB == B)], dp[a][b][c][v1][v2]);
}
if (c < n && (S[all] == 'C' || S[all] == '?')) {
int nowC = c - b + 1;
if (nowC <= C) Add(dp[a][b][c + 1][v1][v2], dp[a][b][c][v1][v2]);
}
}
Add(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: 923ms
memory: 7996kb
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 42 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer Your answer is wrong in testcase 40
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 1425ms
memory: 7904kb
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 808590392 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
wrong answer Your answer is wrong in testcase 40
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%