QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #673634 | #7743. Grand Finale | tumu1t | WA | 296ms | 23084kb | C++20 | 4.0kb | 2024-10-25 03:15:38 | 2024-10-25 03:15:39 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long LL;
using std::cin, std::cout, std::endl, std::vector, std::pair;
std::map<char, int> Card{{'Q', 1}, {'B', 2}, {'G', 0}, {'W', 0}};
const int INF = 100'000;
void Solve()
{
int n, m;
cin >> n >> m;
vector<vector<int>> Dp1(m + 1, vector<int>(m / 2 + 1, -1));
vector<vector<char>> Dp2(m + 1, vector<char>(n + m + 1));
std::string H, D;
cin >> H >> D;
D.insert(0, "0");
vector<vector<int>> Pref(3, vector<int>(m + 1));
for (auto i : H)
{
Pref[Card[i]][0] += 1;
}
for (int i = 1; i <= m; i++)
{
for (int j = 0; j < 3; j++)
Pref[j][i] = Pref[j][i - 1];
Pref[Card[D[i]]][i] += 1;
}
auto CheckOK = [&](int Drawn, int Backflip) -> bool
{
return (m - Drawn <= Backflip * 2);
};
auto Dfs1 = [&](auto self, int Drawn, int Backflip) -> int
{
if (CheckOK(Drawn, Backflip))
return 0;
if (Drawn > m || Backflip < 0)
return INF;
if (Drawn == m)
{
Dp1[Drawn][Backflip] = 0;
return 0;
}
if (Dp1[Drawn][Backflip] != -1)
return Dp1[Drawn][Backflip];
auto &at = Dp1[Drawn][Backflip];
at = INF;
if (D[Drawn + 1] == 'Q')
at = std::min<int>(at, std::max<int>(1, self(self, Drawn + 1, Backflip)));
if (D[Drawn + 1] == 'B')
at = std::min<int>(at, std::max<int>(1, self(self, Drawn + 1, Backflip + 1) + 1));
if (D[Drawn + 1] == 'W')
at = std::min<int>(at, std::max<int>(1, self(self, Drawn + 1, Backflip) + 1));
if (Backflip != 0)
{
if (D[Drawn + 1] == 'Q')
at = std::min<int>(at, std::max<int>(self(self, Drawn + 2, Backflip - 1) - 1, 0));
if (D[Drawn + 1] == 'B')
at = std::min<int>(at, self(self, Drawn + 2, Backflip));
if (D[Drawn + 1] == 'W')
at = std::min<int>(at, self(self, Drawn + 2, Backflip - 1));
}
return at;
};
for (int d = 0; d <= m; d++)
{
for (int b = 0; b <= n + m; b++)
Dfs1(Dfs1, d, b);
}
auto Dfs2 = [&](auto self, int Drawn, int Backflip) -> void
{
if (Drawn > m || Backflip < 0)
return;
if (Dp2[Drawn][Backflip] != 0)
return;
Dp2[Drawn][Backflip] = 1;
int BackflipUsed = Pref[2][Drawn] - Backflip;
int QuickslapUsed = Drawn - 2 * BackflipUsed;
int QuickslapInHand = Pref[1][Drawn] - QuickslapUsed;
if (QuickslapInHand < 0)
{
Dp2[Drawn][Backflip] = 2;
return;
}
if (QuickslapInHand > 0)
{
if (D[Drawn + 1] == 'B')
self(self, Drawn + 1, Backflip + 1);
else
self(self, Drawn + 1, Backflip);
}
if (Backflip > 0)
{
int tmp = (D[Drawn + 1] == 'B' ? 1 : 0) + (D[Drawn + 2] == 'B' ? 1 : 0);
self(self, Drawn + 2, Backflip - 1 + tmp);
}
};
Dfs2(Dfs2, 0, Pref[2][0]);
for (int ans = n; ans <= n + m; ans++)
{
for (int d = 0; d <= m; d++)
{
int BackflipUsed = ans - n;
int BackflipInHand = Pref[2][d] - BackflipUsed;
int QuickslapUsed = d - 2 * BackflipUsed;
int QuickslapInHand = Pref[1][d] - QuickslapUsed;
if (QuickslapUsed >= 0 && BackflipInHand >= 0 && QuickslapInHand >= 0 && Dp2[d][BackflipInHand] == 1 && Dp1[d][BackflipInHand] <= QuickslapInHand)
{
cout << ans << endl;
return;
}
}
}
cout << "IMPOSSIBLE" << endl;
return;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int testcases = 1;
cin >> testcases;
for (int i = 1; i <= testcases; i++)
{
Solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
2 2 6 BG BQWBWW 4 6 GQBW WWWWQB
output:
3 IMPOSSIBLE
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 296ms
memory: 21528kb
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: 162ms
memory: 23084kb
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: 48ms
memory: 8892kb
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: 8ms
memory: 3668kb
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 181st lines differ - expected: '2', found: 'IMPOSSIBLE'