QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706687 | #9463. 基础 ABC 练习题 | Aaronwrq# | 2 | 167ms | 3708kb | C++14 | 1.9kb | 2024-11-03 12:59:03 | 2024-11-03 12:59:05 |
Judging History
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], flag;
string S;
void dfs2(const int p) {
if (max(max(cA, cB), cC) > (3 * n - p) / 2) return;
if (p >= 3 * n) {
if (cABC + cBCA + cCAB < n) return;
if (!S1[cABC] || !S2[cBCA]) return;
flag = 1;
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;
flag = 0;
dfs2(0);
if (flag) ++ans;
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 ((cid <= 2 && n != 10) || (cid > 2 && n != 4)) {cout << "-1\n"; continue;}
ans = 0, dfs1(0);
cout << ans << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 7
Acceptable Answer
time: 167ms
memory: 3636kb
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 -1
result:
points 0.35 the max n you choose to answer is 10
Test #2:
score: 0
Time Limit Exceeded
input:
60 1 1 11 11 CBA 2 111 111 BACACB 3 1111 1111 BCBCACABA 4 11111 11111 CCBACABBBCAA 5 111111 111111 BCACBBABBCCAACA 6 1111111 1111111 BBCBACCAACBCBCAABA 7 11111111 11111111 ACBCCBBAABAABCACCACBB 8 111111111 111111111 BAACACBACCCBAACCBABABBCB 9 1111111111 1111111111 BABCBCAAAAABBCCCACBCBBABACC 10 1111...
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 2
Acceptable Answer
Test #22:
score: 2
Acceptable Answer
time: 107ms
memory: 3708kb
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 25950 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -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:
points 0.2 the max n you choose to answer is 4
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%