QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #723469 | #9463. 基础 ABC 练习题 | hhoppitree | 0 | 2469ms | 3984kb | C++17 | 2.3kb | 2024-11-07 22:24:48 | 2024-11-07 22:24:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 65;
unsigned int f[2][N][N][4];
signed main() {
int T; scanf("%d%*d", &T);
while (T--) {
int n; scanf("%d", &n);
string S1, S2; cin >> S1 >> S2;
vector<int> o1, o2;
for (int i = 0; i <= n; ++i) {
if (S1[i] == '1') o1.push_back(i);
if (S2[i] == '1') o2.push_back(i);
}
string S; cin >> S, S = ' ' + S;
if (n != 60) {
puts("-1");
continue;
}
unsigned int res = 0;
for (int i = 0; i < (int)o1.size(); ++i) {
for (int j = 0; j < (int)o2.size(); ++j) {
int l1 = (!i ? 0 : o1[i - 1] + 1), r1 = o1[i],
l2 = (!j ? 0 : o2[j - 1] + 1), r2 = o2[j], r3 = n - r1 - r2;
if (r3 < 0) continue;
memset(f[0], 0, sizeof(f[0]));
f[0][0][0][(!l1) | ((!l2) << 1)] = 1;
for (int k = 1; k <= n * 3; ++k) {
memset(f[k & 1], 0, sizeof(f[k & 1]));
for (int p = 0; p < k && p <= n; ++p) {
for (int q = 0; p + q <= k && q <= n; ++q) {
int r = k - 1 - p - q;
if (r < 0 || r > n || r - q > r3 || p - r > r1 || q - r > r2) continue;
for (int a = 0; a < 4; ++a) {
if (!f[(k & 1) ^ 1][p][q][a]) continue;
if ((S[k] == '?' || S[k] == 'A') && p - r + 1 <= r1) {
f[k & 1][p + 1][q][a | (p + 1 - r >= l1)] += f[(k & 1) ^ 1][p][q][a];
}
if ((S[k] == '?' || S[k] == 'B') && q - p + 1 <= r2) {
f[k & 1][p][q + 1][a | ((q - p - 1 >= l2) << 1)] += f[(k & 1) ^ 1][p][q][a];
}
if ((S[k] == '?' || S[k] == 'C') && r - q + 1 <= r3) {
f[k & 1][p][q][a] += f[(k & 1) ^ 1][p][q][a];
}
}
}
}
}
res += f[n & 1][n][n][3];
}
}
printf("%u\n", res);
}
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: 1686ms
memory: 3904kb
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 0
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: 2469ms
memory: 3984kb
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 3440830018
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%