QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #600441 | #7743. Grand Finale | zhangboju | WA | 73ms | 34144kb | C++14 | 2.3kb | 2024-09-29 16:35:21 | 2024-09-29 16:35:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2505;
int f[N][N];
bool g[N][N];
int n, m;
string str;
int a[N];
void solve() {
cin >> n >> m;
cin >> str;
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < n; i++) {
if (str[i] == 'Q') ++cnt1;
else if (str[i] == 'B') ++cnt2;
}
cin >> str;
for (int i = 0; i < m; i++) {
if (str[i] == 'B') a[i + 1] = 2;
else if (str[i] == 'Q') a[i + 1] = 1;
else if (str[i] == 'W') a[i + 1] = 0;
}
for (int i = 0; i <= m; i++) {
fill(f[i], f[i] + m + 1, 0x3f3f3f3f);
fill(g[i], g[i] + m + 1, 0);
}
for (int i = 0; i <= m + 1; i++)
f[m][i] = f[m + 1][i] = 0;
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j <= m; j++) {
if (j * 2 >= m - i) {
f[i][j] = 0;
continue;
}
if (a[i + 1] == 0) {
f[i][j] = min(f[i][j], f[i + 1][j] + 1);
}
else if (a[i + 1] == 1) {
f[i][j] = min(f[i][j], max(1, f[i + 1][j]));
}
else {
f[i][j] = min(f[i][j], f[i + 1][j + 1] + 1);
}
if (!j) continue;
if (a[i + 1] == 0) {
f[i][j] = min(f[i][j], f[i + 2][j - 1]);
}
else if (a[i + 1] == 1) {
f[i][j] = min(f[i][j], max(0, f[i + 2][j - 1] - 1));
}
else {
f[i][j] = min(f[i][j], f[i + 2][j]);
}
}
}
g[0][cnt2] = 1;
int sum1 = cnt1, sum2 = cnt2;
for (int i = 0; i < m; i++) {
for (int j = 0; j <= sum2; j++) {
if (!g[i][j]) continue;
int now1 = sum1 - (i - 2 * (sum2 - j));
if (now1 < 0) continue;
if (now1 > 0) {
if (a[i + 1] == 2) g[i + 1][j + 1] = 1;
else g[i + 1][j] = 1;
}
if (j && i + 2 <= m) {
int cnt = (a[i + 1] == 2) + (a[i + 2] == 2);
g[i + 2][j - 1 + cnt] = 1;
}
}
if (a[i + 1] == 1) sum1++;
else if (a[i + 1] == 2) sum2++;
}
for (int k = n; k <= n + m; k++) {
int sum1 = cnt1, sum2 = cnt2;
for (int t = 0; t <= m; t++) {
int tot1 = sum1 - t + 2 * (k - n);
int tot2 = sum2 - k + n;
if (tot1 >= 0 && tot2 >= 0 && f[t][tot2] <= tot1 && g[t][tot2]) {
cout << k << "\n";
return;
}
if (t < m && a[t + 1] == 1) sum1++;
else if (t < m && a[t + 1] == 2) sum2++;
}
}
cout << "IMPOSSIBLE\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin >> T;
while (T--) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5728kb
input:
2 2 6 BG BQWBWW 4 6 GQBW WWWWQB
output:
3 IMPOSSIBLE
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5604kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 73ms
memory: 33612kb
input:
13 184 887 WBQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQG QWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQ...
output:
184 372 316 161 118 534 IMPOSSIBLE 631 183 276 33 160 643
result:
ok 13 lines
Test #4:
score: 0
Accepted
time: 46ms
memory: 34144kb
input:
32 887 278 BQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQQWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQBWW...
output:
887 981 15 18 60 9 108 268 475 17 52 12 IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE 76 14 182 907 537 19 19 233 10 38 111 143 103 159 14 IMPOSSIBLE 225
result:
ok 32 lines
Test #5:
score: 0
Accepted
time: 15ms
memory: 21944kb
input:
120 37 178 BQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBG BWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQQWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQ 21 184 QQBQBWQQQBWQWQBWWBQQG QWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBB...
output:
37 24 41 23 46 22 21 24 31 178 23 26 50 IMPOSSIBLE 23 24 25 24 IMPOSSIBLE 43 17 37 35 46 44 42 25 44 33 33 8 14 21 IMPOSSIBLE 36 32 50 79 IMPOSSIBLE 42 34 42 12 IMPOSSIBLE 32 35 44 13 50 IMPOSSIBLE 47 IMPOSSIBLE 37 16 42 38 IMPOSSIBLE 34 37 30 45 IMPOSSIBLE 46 42 42 34 30 32 27 IMPOSSIBLE 25 14 39 3...
result:
ok 120 lines
Test #6:
score: -100
Wrong Answer
time: 3ms
memory: 5720kb
input:
543 4 37 WBQG BBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWW 2 20 QG BQQQWQBBQQWQQBBWWQWQ 6 47 WBQWWG WWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQB 20 41 WWBWQWQWBWBQWWQBQQQG BWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBB 12 38 BQQWBQBQBWBG QQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQ 3 15 BWG WBQQQWQWBQBBQBW 2 12 WG...
output:
9 4 IMPOSSIBLE 20 12 IMPOSSIBLE IMPOSSIBLE IMPOSSIBLE 8 IMPOSSIBLE 6 IMPOSSIBLE 18 IMPOSSIBLE 18 10 19 19 14 6 IMPOSSIBLE IMPOSSIBLE 7 8 12 IMPOSSIBLE 6 15 13 15 14 13 IMPOSSIBLE 20 5 18 9 11 13 12 10 8 14 9 6 12 14 8 8 IMPOSSIBLE IMPOSSIBLE 19 16 9 15 12 20 10 IMPOSSIBLE 5 12 IMPOSSIBLE 16 9 IMPOSS...
result:
wrong answer 453rd lines differ - expected: '10', found: 'IMPOSSIBLE'