QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673633#7743. Grand Finaletumu1tWA 572ms40372kbC++204.0kb2024-10-25 03:12:152024-10-25 03:12:15

Judging History

你现在查看的是最新测评结果

  • [2024-10-25 03:12:15]
  • 评测
  • 测评结果:WA
  • 用时:572ms
  • 内存:40372kb
  • [2024-10-25 03:12:15]
  • 提交

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>((n + m + 3) / 2, -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();
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

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: 3544kb

input:

2
3 8
QBG
BBBWBWWW
3 8
QBG
BBBWBWWW

output:

3
3

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 280ms
memory: 22340kb

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: 156ms
memory: 25500kb

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: 43ms
memory: 10004kb

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: 0
Accepted
time: 8ms
memory: 3612kb

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:

ok 543 lines

Test #7:

score: 0
Accepted
time: 8ms
memory: 3844kb

input:

558
11 32
WBBBQWQWQBG
WBWQBWBQQBBBWBWQBBBWWQWBBQBBQBWW
17 23
WQWQBQBWWBQBBBQWG
BWQBBWQWBQQQWWWWWQWBBWB
10 22
BBWWQQQWBG
BQWBWQBQQBWWQWQWQBWQQQ
16 22
BBQWBQQWQQQWWWWG
QQQWBQWQWWQQWWWQBQQQBQ
14 32
BQQQWWWWQQBBQG
QBQQBQWBWWWWWWQWWQBQQQWQQWQQBWQQ
1 16
G
BBQQWWBBBBQBBQWW
16 49
QQQQWQQQQQBWQBBG
BWBWQWBWWW...

output:

11
17
10
16
14
IMPOSSIBLE
16
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
16
4
16
16
7
IMPOSSIBLE
15
15
16
10
17
16
9
11
16
IMPOSSIBLE
8
20
7
IMPOSSIBLE
15
10
11
16
18
7
15
19
9
7
8
IMPOSSIBLE
IMPOSSIBLE
14
18
4
IMPOSSIBLE
IMPOSSIBLE
10
11
16
10
13
16
6
16
IMPOSSIBLE
19
IMPOSSIBLE
17
IMPOSSIBLE
20
8
10
15
10
17...

result:

ok 558 lines

Test #8:

score: 0
Accepted
time: 8ms
memory: 3628kb

input:

566
9 16
BBWWQWWQG
QBBWQWBBQWBWQWWW
3 7
BWG
BWBQQQB
10 15
BQWWBBWBWG
QBBWBWBQBQQQQBW
8 17
QBQQBBQG
QQWBBBQWWWBQWWQQQ
18 46
WBQBQQQWQQQQBQQWWG
QQBQWWQBBWBQQBQWWWWWBBWWBWQBQWQQQWWWQWQWWWQQQB
20 38
WQBQWQQBQQWWQWQWQWBG
BBBBBBQQBBQQQBBBWBBQWBWBBWBBQBQBWBBQWW
20 17
QBQQBWBBBBWWQWBBQWWG
QWWBWQQQWWBWQWQQB
...

output:

9
3
10
8
18
20
20
IMPOSSIBLE
19
IMPOSSIBLE
10
15
IMPOSSIBLE
12
7
IMPOSSIBLE
8
13
15
6
12
11
13
5
7
20
11
12
16
IMPOSSIBLE
IMPOSSIBLE
11
4
14
IMPOSSIBLE
20
12
10
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
9
15
14
11
19
17
5
12
20
15
14
16
20
17
9
10
17
7
11
13
18
15
7
IMPOSSIBLE
IMPOSSIBLE
4
18
IMPOSSIBLE
12
6...

result:

ok 566 lines

Test #9:

score: 0
Accepted
time: 8ms
memory: 3844kb

input:

549
16 26
WQWWBBQWWWWQQBQG
WWWWBWWBWBWBQWBWBBWQBQQQWW
1 16
G
QQWQQWWWBBQQWWWQ
19 36
QBQWWWBWBQWQWQBWQBG
BWQQBQWQWWBQBBWBBQQWQWWWWWWQBWWWBQWQ
8 17
BWBWWBBG
QWWBQBWBBBQQQBWWB
6 21
QQBQWG
WQQWBWQWWQBBWQWQQQQQB
2 46
WG
QBWQQWQWWWWBWQQQBBWWBBWWWQQQBQBBWBBWQBWBBBWQBW
6 27
BQWWWG
BWBBWBWQWQWBWWQBBBWQBWWQQB...

output:

16
IMPOSSIBLE
19
8
6
IMPOSSIBLE
14
13
20
7
9
IMPOSSIBLE
11
17
16
18
19
19
19
9
12
16
18
IMPOSSIBLE
11
12
IMPOSSIBLE
11
13
19
13
IMPOSSIBLE
20
IMPOSSIBLE
11
17
10
11
IMPOSSIBLE
17
5
IMPOSSIBLE
13
20
19
18
13
13
IMPOSSIBLE
13
9
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
8
16
10
15
20
17
13
18
10
20
8...

result:

ok 549 lines

Test #10:

score: 0
Accepted
time: 10ms
memory: 3664kb

input:

370
2 37
WG
BWBBWQQWWBQQQWBQBWBWWBWBQQBBWQQQQWBWQ
9 1
WQBWBBBBG
B
7 18
BWQBQQG
QBBWBBWBQBBQQQWQWB
2 41
WG
QBQBQWWBQWBBQBWBQBWBQWBQBBQQQQWWBWQBBQBWW
5 52
WQWQG
BWWQQBQQWBWBBQQBQQWWBBBBQQQWBBQQBQWWBWWWBWBQWWQWWWBB
9 71
WBWBBBQWG
QWBWBWBQWQWBQQQQQWBBBWWWQWQBWBWWQBBBBQQQQQBBQBQWBWQBWQQWBBQQWQQWWWBQQWQ
9...

output:

IMPOSSIBLE
9
7
IMPOSSIBLE
IMPOSSIBLE
15
9
10
3
10
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
10
IMPOSSIBLE
7
IMPOSSIBLE
6
16
IMPOSSIBLE
15
4
6
12
10
13
11
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
17
IMPOSSIBLE
10
8
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
7
IMPOSSIBLE
IMPOSSIBLE
21
9
13
10
6
IMPOSSIBLE
...

result:

ok 370 lines

Test #11:

score: 0
Accepted
time: 328ms
memory: 29376kb

input:

5
1000 2500
QBBWQQWQQWQQWBQQBQWWBWBQWWBBQWBBWWQWQWQQWQQQBQQWQWBBBQBQQQWBBQWBWWBWQQWWQWQWWQBBWQQQBWBBBQWQQBBWBWWBWBQQWQWWQQBQQBBBQWWWWWWQQQQQBWWBWWQWWQWQQWWBQQWQWBBWQQWQQWBBWQQWWQBWQWWQWWWWBBQBWWBWWBQWQBBBWBQWQBBBBWWQBQQQWQWBBQQQQBQBQBWQWWBQBWQWWQQQBQBWQWQWQBQBQQBQBBQQQWQBBBBQQBBWBBBBBWQWBWWBQBWBWBBB...

output:

1000
1000
1000
1000
1000

result:

ok 5 lines

Test #12:

score: 0
Accepted
time: 330ms
memory: 40372kb

input:

4
2500 2500
WBQQQWBBQBQQBQQBWQWBQQWBQBBBBWBBBBBWQWBWQWQBBWQQWBBWWBQWWBQQBWQQQWWQQQQBBQWWQBQWQWBWWBWBQQWQWWBWBWWBWQQBQWBQBBWBWQBWWQQQQQBWBBWQQWBQWBBQBWQBWWQWQQBQQWWQWQQBWWBQBQWQWBQQQQWQWWWWWBQWBWWWWQBWWWBBQBBWWWWWWBWBBBBWWBWQQWQQWBWBQQWBBBQQBQWWBBBBQWBWQQBBWWBBQWQBQQBQWBBQQBQWWBBBQWBQQQWWBWBWWWWWWQWW...

output:

2500
2500
2500
2500

result:

ok 4 lines

Test #13:

score: 0
Accepted
time: 389ms
memory: 25648kb

input:

7
192 2500
QBBBBQBQWWQQQBQQWWBQBQWWQBBWWBQWBWQQWBQWQWQQBQBWWQQQQQWQBQBQWWWQQQQQBQBBQBWQBWQBWBBBBQWQBBBQWBQQBQQBBWQQWBQQBBWBWQQQQBQWQWBQWWQQQQWBWBWBQQWBBQQQBWBBBWQBQWQWWQWWBQWWWBBQBWWWQWBWBQQWBQQBWQBQBBQG
BWWBBQWBBWBBQWQBBWWQQWQWBBQWWWWBQBWWWQWBQBWWQBBQBQQWBBBQWWWWBWWBBWQQQQWWBBWQQQBBQBQWWWWWBWBQBBBW...

output:

516
378
482
460
358
486
483

result:

ok 7 lines

Test #14:

score: 0
Accepted
time: 371ms
memory: 24992kb

input:

7
325 2500
WQBQWQQBQWWBBWWBBBWWBQBQWQQQBWWQQBQWBBQWQQQBWBWQQBWWWWBQQWBWBQQBBWQWBQBBQBWWQBWQQWQQWBBWQWBBWBWQBWWBQBQQWQWWWWQWWQWQBQQBWBWBWBWQBWWBQWBWWBBBBBBWWQQQQQBQBQWBBBWQQQBWQWWQBBBBQBBWWBBWWWWBWBWBWQBBBWBBWBBQWBWWQQBWWWBQBQWBBQBQBQWQQBBWWQWBWBBWQQBQBWQQWWBBWQBBWQBQBQBBQQQBWBBWQWBWWWWBBBBBQQQQWWQBW...

output:

325
520
438
335
339
414
286

result:

ok 7 lines

Test #15:

score: 0
Accepted
time: 358ms
memory: 25052kb

input:

7
159 2500
BBWWBBWQBQQWWBBWWQWWBWQBQQWQBWBWBBWWQBQBBQBQWQWWWWBQWBWWBWQWBWBWQQWQWWBQQQQWWQBWWBQBQWBBBWBWBWBWQQWBWQBWBWBQWBWBQWQBBBWQBBWWQQBQQQWWBBWWQWWQBBWWQWQWBQWWBWWBWQG
WWQBWBWBQQBWQQBWWWWQBQQBQBQWQWBWWWBBQBWQBQWWQBWWWBWBWWWWBWWBWBBWWWQWBQQWQQBQBBWQWBQWBWWWWBBWBQBBQBBBWBQWWWWQQBQQQBQQBWQQWQWBBQWQW...

output:

570
576
307
351
291
418
375

result:

ok 7 lines

Test #16:

score: 0
Accepted
time: 379ms
memory: 25552kb

input:

7
384 2500
WBWBWBWWWWBWBBBWBQBBBQBWBQQBQBQWWQQQBBQQBWQWBBWBWQQQBBWQBQWBBBQQWBQWQBQBBQBWBWBBQBBBWBBQQQBWBWWBQQQQWQBQQWWWWQQBBBQQQWBBWWWBWBBWBWQQWBWWQWBWWBBBQBWQWQQWQQWWBQBWWBWBBWQBBBBBQBBQQQBQWBBWWBBWBWWBQBWWQWBWBWWBQQBBQQQQBWWQQQQWQBQBQWQQWBWQBBBWBQWBQQWWWBBWWBBWQWWWWWWBBBBBBQQQBQWQQQQWBBWWWBBWQBBWB...

output:

384
451
IMPOSSIBLE
376
799
681
455

result:

ok 7 lines

Test #17:

score: 0
Accepted
time: 565ms
memory: 20988kb

input:

34
410 1517
BBQWQWQBWQQBBQQBQQQWQWQWBBBQWBQBBQWWBBBQBQBWBBQBWWBWBQQBQBBQBWWWWQBBWWWWBBWBBBWBQQWQWQQWWQBBWWBBWBWQQQQQWQBQQBBQWQQQBBBQQQWWWWWWWBQQQBWWBWWBBQQQBWQQBQQWWBBWQBQQQQQWBWWWBQBBQWWWWQBWQWBWBQWGQQWWBBWWWWQBBQBBBBBQBQWQQBBBWQWBBWWWBWQWBBBWQBQWQBBWQQWWWBQBWQWQBQBQWQQWWWWBBBQWWWQQQBWWWBQWQWQQBQWW...

output:

410
370
305
308
416
61
236
458
183
463
483
316
IMPOSSIBLE
255
475
305
486
153
193
249
IMPOSSIBLE
264
155
394
364
336
153
343
394
471
415
319
421
280

result:

ok 34 lines

Test #18:

score: 0
Accepted
time: 12ms
memory: 3568kb

input:

1627
19 34
BQWWWWBQWQWBBGQWWQB
QBBQQQWWBBBQBWBQWBBBBWBWQBQWBWBQQQ
20 1
WBBQBBBWWBGWBQWQQBQQ
W
2 38
GW
BQQBQBQBBWQQWQBBBBBQBQBQQBQQBBWBQQBBBW
15 15
QWBQWQQWWWWQWWG
WWBQBBBBQWWWBWB
15 2
QWQBWWQGBWQBWWW
WB
11 24
WBQWWBQWGBQ
BWQWBQBWQWBQWQWWWBQQWQWW
8 37
QGWWQBWQ
WBQBWBBBBBQQQWWQBWWWBQWWWQQBBWWBQWWWB
11...

output:

19
20
IMPOSSIBLE
15
15
11
12
11
3
11
IMPOSSIBLE
13
6
17
13
9
11
10
5
12
14
14
15
11
14
19
17
18
14
10
IMPOSSIBLE
14
14
5
10
12
7
10
IMPOSSIBLE
7
6
IMPOSSIBLE
8
9
17
10
IMPOSSIBLE
4
17
18
14
IMPOSSIBLE
20
8
13
11
11
11
17
8
14
12
5
14
13
19
IMPOSSIBLE
15
6
4
4
16
10
17
11
17
IMPOSSIBLE
13
15
IMPOSSIB...

result:

ok 1627 lines

Test #19:

score: 0
Accepted
time: 24ms
memory: 3760kb

input:

661
14 69
BBWBWWGWBWQBBB
BWWBBQBBWQBBBBQBBWQQBBQQQBWWWQQBQWBBQWWBWWBWQBWBBBWWBQQBBWBQQBWQWQQQB
18 67
QQGWWBBWWBBWBBQWQW
WWQQWBWBQBBWQQQBWBBWWWQQWQWWWBWQWWWWBQBBBWWBBQBQQQQBWWWQBBQQBBBBQWB
34 7
QQQQWQQWQWWWWQWBBBQBBQWQGWBBQWBQBQ
BQWQQWQ
17 85
BWBGQWBBBBBBBQQWW
BBQQQQBBWWBWWBBWQQWQBBWWWQWQWBQQBQWQBWWQ...

output:

14
18
34
17
49
18
49
50
11
40
10
25
21
48
25
34
24
29
IMPOSSIBLE
9
46
44
37
21
30
44
14
19
IMPOSSIBLE
32
20
IMPOSSIBLE
33
21
42
28
16
16
47
50
35
IMPOSSIBLE
IMPOSSIBLE
50
15
37
36
IMPOSSIBLE
24
25
19
43
39
18
13
IMPOSSIBLE
28
35
10
36
36
47
45
41
39
IMPOSSIBLE
49
9
20
21
24
24
35
13
18
8
47
48
49
31...

result:

ok 661 lines

Test #20:

score: 0
Accepted
time: 121ms
memory: 4916kb

input:

168
67 58
WBQBBWWQWWWWQQWQWWQQBBWQQBBGWQWWWBWQBQBWQQBQQQWBBBBQBBWWWQWQWBQWQBW
BQWQBQQWWBBQWWBWBBWQWWQQWBBQQQBBWQWWBBQQQWQBQQQBWWBBBQWBQW
73 247
QBQBQQGBQBWQBWBBBQWWWBWWQWBQBBWWWBWBQBBWQQQQWQQQWWWBQQBWWQWBBBQQBWWBWWBQQ
WWQQQWQBWWQQWWWQWWQBBWWWBBBBWWWBBQBBWWQBBWQQWBWQWWBBQBQWWQQQQBWWWWBQBWQBBQQBBBQWQB...

output:

67
73
35
33
61
10
66
78
59
67
19
51
69
44
81
25
116
56
64
99
65
49
89
92
81
45
IMPOSSIBLE
85
IMPOSSIBLE
IMPOSSIBLE
69
87
81
68
63
31
45
97
81
18
99
IMPOSSIBLE
IMPOSSIBLE
89
78
55
60
31
130
54
IMPOSSIBLE
95
76
97
47
79
99
48
109
43
57
93
92
79
IMPOSSIBLE
40
33
23
IMPOSSIBLE
100
74
30
97
53
74
IMPOSSI...

result:

ok 168 lines

Test #21:

score: 0
Accepted
time: 257ms
memory: 6884kb

input:

78
69 670
BQQWBWQWBBBBBQQBWBBQWQQBQWBWQWQWBWWWQGQBQQQWBQQQQQQBQBQBBBQWBBWQBBWWB
QWWBBWQWQBWWQBWWQQWBQBQBBQWWWQWBWQQBWWBBWBWBWBQBBQQBWBBQWWQWWBBQQQWQQBBBWBWWWQBBWQWWQQQBBWBBWBBBQWBQBQWWWBBBWBQQQWWWBWBWQBWWBQBWWBBQBQWQQQQWWWWQBWBBBBWWBQWWBQBBQWWWQWBQWBBWQQQWWBWQBWQQWBWWQQWQWQWQQWQBQQWQQWWWWBBWWBQBQWBQ...

output:

97
110
56
121
157
129
110
70
190
72
136
155
116
108
133
158
132
91
101
107
195
IMPOSSIBLE
95
123
131
192
IMPOSSIBLE
21
82
149
129
IMPOSSIBLE
94
216
111
87
194
166
93
171
108
114
108
174
85
84
101
88
32
148
112
102
188
158
106
141
34
200
115
160
60
104
55
198
110
172
33
76
62
188
189
119
133
72
52
99...

result:

ok 78 lines

Test #22:

score: 0
Accepted
time: 572ms
memory: 19624kb

input:

38
50 2202
BBWWQBWWQBBWWBQWQWBQWBWBBGWBWQBWQQBWQQWQBWBQWQQQBQ
WBBQQBBBQQQBBWQBBBQWBBBBWBWWQQQWWWQQWBBBQQBWBWWWQWQQWBQBBWBWBBBQQQBBBBQBWQWWQQWBWWWBWBBQWQBWQWBQWWBBQBBBQWBBWQQBWWWBWWWBBWBWWBQWWWQWQQQQWQWWWWQWQBBBWQQBQWBWBBWQQBQBQWQWBBQBQQWQQQQWQQQBQBWBBQQQQBWQWQBBWBQQBWBWQBWWBBBWBBQWBQWBBBBWWWQBWQWWQB...

output:

534
202
261
373
220
281
106
173
274
195
IMPOSSIBLE
297
154
169
527
255
531
447
144
195
189
24
75
81
52
243
136
254
IMPOSSIBLE
292
271
222
213
128
299
478
163
231

result:

ok 38 lines

Test #23:

score: 0
Accepted
time: 418ms
memory: 29076kb

input:

17
2449 1335
QQQBBBBWWWWBWWWBBWWQBWBWQWBBBQWQWWBWBQBBQWWQBBWQBWBBQQWBQQBQQQQBWWBQBBBQQQBWBQWBQQWWWQQBBWWWQQWWBQBQWBQQBQQQWBWWQBWWBWBQQBWQBWWWBWQBBBBBQWBQBQBQBQWWQWQBQQQBWWQBWQQBWQWQWWQQBWQWWQWBWBWBBBWQWBBBQWWBQQBQWQQBBWBWBBBWQQBWWQQQBBWWBWWWQBBWBQWWWBQBBWQWQBQQQQBBWWWQQWWBBWWQQQWQWWBQWBQQQQQBBBBWBQB...

output:

2449
1337
1453
1679
1004
662
552
1399
536
2156
606
2438
1992
1738
1194
2142
2214

result:

ok 17 lines

Test #24:

score: 0
Accepted
time: 10ms
memory: 3920kb

input:

156
455 9
QWQWQWBBBQQQQWBQWQBQWQBBBBWWQBBWWQBWQWBQBWQBQQBWBQBQBBQWWBWBQQWQQQBBBQBQWQWQQBQWBBWBBQWWBQWQQQQQQWBWWQQWQQBQBQBBWBWQQQWWQQQQWWQQWQQQBBBBBBBBQQQWWWWBQQQWBBBBWWBWWWBQBBQQWWWWQBWWWWBBWWQWQWBWQBBBQBWBQWQBBBWWWQWBBWBBBWWWBBWWBBBBWWBWQBQQBBWQQBWBWWBWBQQBQQBQBBBQWBWBQWQBQWQQQBBBWWQQWQQWQQQWQWWWWQ...

output:

455
298
372
237
185
256
189
236
433
399
245
29
83
498
60
404
104
147
413
173
114
339
64
78
172
89
357
96
401
371
439
342
465
287
399
492
340
300
369
272
26
460
379
277
122
205
138
438
152
123
270
206
152
399
147
201
252
24
183
308
76
428
304
304
375
115
17
240
259
236
96
64
397
358
500
334
113
466
2...

result:

ok 156 lines

Test #25:

score: 0
Accepted
time: 7ms
memory: 3548kb

input:

5915
3 7
WGB
BQBQWWB
1 10
G
WWWQWQQQBB
2 2
QG
WQ
2 3
BG
WBW
3 1
QBG
Q
2 3
BG
WQQ
4 1
QBGW
Q
2 10
WG
WQBWBBQQQQ
4 6
BQWG
QWQBBW
3 10
GBQ
WBQQQWQBBB
3 8
QWG
QWQQBBBQ
4 1
WQBG
Q
5 7
BBGWW
WBBWQWB
4 1
BGQB
B
2 8
GB
BBWQWBQQ
5 6
BGWQB
WWWQWW
1 2
G
BQ
4 1
BBGQ
W
2 10
QG
BWQBBWBWBB
5 7
BBGWW
BQWWWBQ
5 4
BQ...

output:

4
IMPOSSIBLE
IMPOSSIBLE
3
3
3
4
IMPOSSIBLE
4
4
IMPOSSIBLE
4
5
4
4
5
IMPOSSIBLE
4
3
6
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
4
5
3
IMPOSSIBLE
4
4
3
5
IMPOSSIBLE
3
IMPOSSIBLE
IMPOSSIBLE
4
IMPOSSIBLE
IMPOSSIBLE
5
IMPOSSIBLE
4
3
IMPOSSIBLE
IMPOSSIBLE
5
IMPOSSIBLE
IMPOSSIBLE
4
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBL...

result:

ok 5915 lines

Test #26:

score: 0
Accepted
time: 15ms
memory: 3840kb

input:

5011
5 1
GQQBQ
B
4 3
GQBB
WWQ
4 2
WQQG
BB
2 8
GB
BWQQWBBQ
3 7
WWG
BBQBWBW
6 9
QBQQBG
WBBQQQBBB
6 2
QQBGQW
QB
1 7
G
BBQBQWW
5 3
BQWBG
BBW
3 4
BQG
BQWB
1 7
G
QQQBBWB
4 7
GBBB
QBQQWBW
2 6
QG
WBBBWQ
2 11
QG
WQQQQBBQWBB
4 4
GWQQ
WBBW
3 3
WWG
WQW
5 5
QBGWQ
QQBQB
5 4
GWQBB
WQBW
1 1
G
Q
4 8
QBGW
BWBWWBBB
2 ...

output:

5
4
4
4
IMPOSSIBLE
6
6
IMPOSSIBLE
5
3
IMPOSSIBLE
4
IMPOSSIBLE
IMPOSSIBLE
4
IMPOSSIBLE
5
5
IMPOSSIBLE
4
IMPOSSIBLE
5
6
IMPOSSIBLE
IMPOSSIBLE
3
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE
2
4
IMPOSSIBLE
4
IMPOSSIBLE
6
IMPOSSIBLE
4
5
6
2
IMPOSSIBLE
5
IMPOSSIBLE
6
6
IMPOSSIBLE
7
2
6
4
4
4
6
I...

result:

ok 5011 lines

Test #27:

score: -100
Wrong Answer
time: 13ms
memory: 3568kb

input:

4567
1 9
G
QBQBWWBQQ
7 5
GBQWQBW
BWWQW
10 6
QWGBQQBWWB
WQBQQB
4 6
WGBW
WWWBBQ
7 3
QGQBBQB
WBB
6 4
WBWWBG
BQBQ
6 2
QQWGWB
BB
4 10
GBBW
QQBQQWQBBW
10 9
QBQWQWBBQG
QQBBBWWQB
7 7
GBQBWBB
BBQBWWQ
9 3
WQQQBWBGQ
QQB
9 5
BWWWWWQGW
BWBQB
6 4
WQBGWW
BWWW
5 6
WGQWQ
BQQWQB
8 10
WBQQBQQG
BBWQQQWQWQ
7 4
WWWGWQQ
Q...

output:

IMPOSSIBLE
7
10
IMPOSSIBLE
7
6
6
4
10
7
9
9
6
5
8
IMPOSSIBLE
6
3
6
6
8
4
9
7
IMPOSSIBLE
10
5
6
5
5
IMPOSSIBLE
10
10
4
IMPOSSIBLE
4
7
2
10
9
10
4
3
5
4
9
8
3
9
9
IMPOSSIBLE
6
IMPOSSIBLE
10
7
IMPOSSIBLE
5
6
7
5
10
8
7
3
4
3
8
IMPOSSIBLE
5
3
IMPOSSIBLE
8
5
5
6
6
IMPOSSIBLE
3
IMPOSSIBLE
5
10
6
7
5
7
7
9...

result:

wrong answer 1481st lines differ - expected: '9', found: 'IMPOSSIBLE'