QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263145#7743. Grand Finaleucup-team1447WA 110ms107464kbC++142.3kb2023-11-24 15:56:442023-11-24 15:56:46

Judging History

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

  • [2023-11-24 15:56:46]
  • 评测
  • 测评结果:WA
  • 用时:110ms
  • 内存:107464kb
  • [2023-11-24 15:56:44]
  • 提交

answer

// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
int T, n, m, p[5005][5005], dp[5005][5005], c1[5005], c2[5005];
std::string s, t;
bool check(int size)
{
    for (int i = 0; i <= c1[n]; ++i)
        if (p[i][size - m] && dp[p[i][size - m]][i] <= c2[p[i][size - m]] - (size - m))
            return true;
    return false;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin >> T;
    while (T--)
    {
        std::cin >> m >> n >> t >> s;
        s = t + s;
        n = n + m;
        for (int i = 0; i != n; ++i)
        {
            c1[i + 1] = c1[i] + (s[i] == 'Q');
            c2[i + 1] = c2[i] + (s[i] == 'B');
        }
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= n; ++j)
                p[i][j] = 0;
        p[0][0] = m;
        for (int i = 0; i <= c1[n]; ++i)
            for (int j = 0; j <= c2[n]; ++j)
            {
                if (i < c1[p[i][j]])
                    p[i + 1][j] = std::min(n, p[i][j] + 1);
                if (j < c2[p[i][j]])
                    p[i][j + 1] = std::min(n, p[i][j] + 2);
            }
        for (int i = 0; i <= n; ++i)
            dp[n][i] = 0;
        for (int i = n; i--;)
            for (int j = 0; j <= n; ++j)
            {
                dp[i][j] = INT_MAX / 2;
                if (j)
                    dp[i][j] = std::min(dp[i][j], dp[i + 1][j - 1 + (s[i] == 'Q')] - (s[i] == 'B'));
                dp[i][j] =
                    std::min(dp[i][j],
                             std::max(1,
                                      dp[std::min(n, i + 2)][j + (s[i] == 'Q')] - (s[i] == 'B') + 1));
            }
        // for (int i = 0; i <= c1[n]; ++i)
        //     for (int j = 0; j <= c2[n]; ++j)
        //         std::cout << p[i][j] << " \n"[j == c2[n]];
        // std::cout << c1[n] << ' ' << c2[n] << std::endl;
        if (p[c1[n]][c2[n]] == 0)
        {
            std::cout << "IMPOSSIBLE" << std::endl;
            continue;
        }
        // std::cout << check(3) << std::endl;
        int l = m, r = n;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        std::cout << l << std::endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

2
3 8
QBG
BBBWBWWW
3 8
QBG
BBBWBWWW

output:

3
3

result:

ok 2 lines

Test #3:

score: -100
Wrong Answer
time: 110ms
memory: 107464kb

input:

13
184 887
WBQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQG
QWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQ...

output:

1071
1881
2601
712
1006
2557
IMPOSSIBLE
2310
1506
1766
33
160
2452

result:

wrong answer 1st lines differ - expected: '184', found: '1071'