QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706639 | #9463. 基础 ABC 练习题 | Aaronwrq# | 0 | 1ms | 3620kb | C++14 | 1.7kb | 2024-11-03 12:44:59 | 2024-11-03 12:45:01 |
answer
#include <bits/stdc++.h>
#define MAXN 185
using namespace std;
int T, cid, n, ans;
int cA, cB, cC, cAB, cBC, cCA, cABC, cBCA, cCAB;
bool S1[MAXN], S2[MAXN];
string S;
void dfs2(const int p) {
if (p >= 3 * n) {
if (cABC + cBCA + cCAB < n) return;
if (!S1[cABC] || !S2[cBCA]) return;
++ans;
return;
}
if (S[p] == 'A') {
if (cBC) {
--cBC, ++cBCA;
dfs2(p + 1);
++cBC, --cBCA;
}
if (cC) {
--cC, ++cCA;
dfs2(p + 1);
++cC, --cCA;
}
++cA;
dfs2(p + 1);
--cA;
}
else if (S[p] == 'B') {
if (cCA) {
--cCA, ++cCAB;
dfs2(p + 1);
++cCA, --cCAB;
}
if (cA) {
--cA, ++cAB;
dfs2(p + 1);
++cA, --cAB;
}
++cB;
dfs2(p + 1);
--cB;
}
else {
if (cAB) {
--cAB, ++cABC;
dfs2(p + 1);
++cAB, --cABC;
}
if (cB) {
--cB, ++cBC;
dfs2(p + 1);
++cB, --cBC;
}
++cC;
dfs2(p + 1);
--cC;
}
return;
}
void dfs1(const int p) {
if (p >= 3 * n) {
int cA = 0, cB = 0, cC = 0;
for (int i = 0; i < 3 * n; ++i) {
if (S[i] == 'A') ++cA;
else if (S[i] == 'B') ++cB;
else ++cC;
}
if (cA != n || cB != n || cC != n) return;
dfs2(0);
return;
}
if (S[p] != '?') dfs1(p + 1);
else {
S[p] = 'A', dfs1(p + 1);
S[p] = 'B', dfs1(p + 1);
S[p] = 'C', dfs1(p + 1);
S[p] = '?';
}
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 != 2) {cout << "-1\n"; continue;}
dfs1(0);
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: 1ms
memory: 3620kb
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 2 -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
result:
wrong answer Your answer is wrong in testcase 2
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 1ms
memory: 3620kb
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 75 -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
result:
wrong answer Your answer is wrong in testcase 2
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%