QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#243126#7743. Grand Finaleqkm66666WA 98ms30184kbC++172.8kb2023-11-07 21:16:382023-11-07 21:16:38

Judging History

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

  • [2023-11-07 21:16:38]
  • 评测
  • 测评结果:WA
  • 用时:98ms
  • 内存:30184kb
  • [2023-11-07 21:16:38]
  • 提交

answer

#include<iostream>
using namespace std;
const int maxn=2600;
int T,n,m;
int dp[maxn][maxn];
int cur,cnt[2];
int Ans;
string H,P;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        cin>>H;
        cin>>P;
        for(int i=0;i<=m;i++){
            for(int j=0;j<=m;j++){
                dp[i][j]=m+1;
            }
        }
        for(int i=0;i<=m;i++){
            dp[m][i]=0;
            dp[m-1][i+1]=0;
        }
        for(int i=m;i>0;i--){
            for(int j=m;j>=0;j--){
                if(i>=2&&P[i-1]!='G'){
                    if(P[i-2]=='B'&&j>=1){
                        dp[i-2][j]=min(dp[i-2][j],dp[i][j]);
                    }
                    if(P[i-2]=='Q'){
                        dp[i-2][j+1]=min(dp[i-2][j+1],max(dp[i][j]-1,0));
                    }
                    dp[i-2][j+1]=min(dp[i-2][j+1],dp[i][j]);
                }
                if(i>=1){
                    if(P[i-1]=='B'&&j>=1){
                        dp[i-1][j-1]=min(dp[i-1][j-1],dp[i][j]+1);
                    }
                    if(P[i-1]=='Q'){
                        dp[i-1][j]=min(dp[i-1][j],max(dp[i][j],1));
                    }
                    dp[i-1][j]=min(dp[i-1][j],dp[i][j]+1);
                }
            }
        }
        Ans=m+1;
        cnt[0]=0;
        cnt[1]=0;
        cur=n;
        for(int i=0;i<n;i++){
            if(H[i]=='B'){
                cnt[0]++;
            }
            if(H[i]=='Q'){
                cnt[1]++;
            }
        }
        for(int i=0;i<m;){
            if(dp[i][cnt[0]]<=cnt[1]){
                Ans=cur;
                break;
            }
            if(cnt[0]==0&&cnt[1]==0){
                break;
            }
            if(cnt[0]){
                cnt[0]--;
                if(P[i]=='B'){
                    cnt[0]++;
                }
                if(P[i]=='Q'){
                    cnt[1]++;
                }
                cur++;
                i++;
                if(i<m){
                    if(P[i]=='B'){
                        cnt[0]++;
                    }
                    if(P[i]=='Q'){
                        cnt[1]++;
                    }
                    i++;
                }
            }
            else{
                cnt[1]--;
                if(P[i]=='B'){
                    cnt[0]++;
                }
                if(P[i]=='Q'){
                    cnt[1]++;
                }
                i++;
            }
        }
        if(Ans==m+1){
            puts("IMPOSSIBLE");
        }
        else{
            printf("%d\n",cur);
        }
    }
    //system("pause");
    return 0;
}
/*
2
2 6
BG
BQWBWW
4 6
GQBW
WWWWQB

*/

详细

Test #1:

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

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

input:

2
3 8
QBG
BBBWBWWW
3 8
QBG
BBBWBWWW

output:

3
3

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 98ms
memory: 30184kb

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: 58ms
memory: 29400kb

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: 14ms
memory: 17728kb

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

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
IMPOSSIBLE
9
6
12
14
8
8
IMPOSSIBLE
IMPOSSIBLE
19
16
9
15
12
20
10
IMPOSSIBLE
5
12
IMPOSSIBLE
16
...

result:

wrong answer 43rd lines differ - expected: '14', found: 'IMPOSSIBLE'