QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #358652 | #7743. Grand Finale | Baiyu0123 | WA | 22ms | 47732kb | C++14 | 1.7kb | 2024-03-19 22:03:01 | 2024-03-19 22:03:01 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define ll long long
using namespace std;
const int maxn=3010,lim=1e9;
string s0,s;
bool f[maxn][maxn];
int g[maxn][maxn];
int c1[maxn],c2[maxn];
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
memset(g,63,sizeof(g));
int T;cin>>T;
while (T--) {
int n,m,k,ans=lim;
cin>>n>>m;
cin>>s0>>s;s="0"+s+"WW";
for (int i=0;i<s0.size();i++) c1[0]+=(s0[i]=='Q'),c2[0]+=(s0[i]=='B');
for (int j=1;j<=m+1;j++) c1[j]=c1[j-1]+(s[j]=='Q'),c2[j]=c2[j-1]+(s[j]=='B');
f[0][0]=1;
for (int i=0;i<m;i++) {
for (int j=0;j<=c2[i];j++) {
if (f[i][j]==0) continue;
if (j!=c2[i]) f[i+2][j+1]=1;
assert(i-2*j>=0);if (c1[i]>i-2*j) f[i+1][j]=1;
}
}
for (int j=0;j<=c2[m];j++) {
g[m][j]=0;g[m+1][j]=0;
}
for (int i=m-1;i>=0;i--) {
for (int j=0;j<=c2[i];j++) {
g[i][j]=lim;
if (j!=0) g[i][j]=min(g[i][j],
max(0,g[i+2][j-1+c2[i+1]-c2[i]]-c1[i+1]+c1[i]));
g[i][j]=min(g[i][j],max(0,g[i+1][j+c2[i+1]-c2[i]]-c1[i+1]+c1[i])+1);
}
}
for (int i=0;i<=m+1;i++) {
for (int j=0;j<=c2[i];j++) {
if (f[i][j]&&g[i][c2[i]-j]<=i-2*j) {
// cout<<i<<" "<<j<<" : "<<c2[i]-j<<" "<<g[i][c2[i]-j]<<endl;
ans=min(ans,n+j);
}
}
}
for (int i=0;i<=m+1;i++) {
for (int j=0;j<=c2[i];j++) {
f[i][j]=0;g[i][j]=lim;
}
}
for (int i=0;i<=m+1;i++) c1[0]=c2[0]=0;
if (ans>=lim) cout<<"IMPOSSIBLE\n";
else cout<<ans<<endl;
}
}
/*
2
4 6
1 1 8
7 2 5
1 1 7
3 2 6
8 1200000
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
100000 1 100000
100000 1 12345
100000 2 100000
100000 2 12345
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 40536kb
input:
2 2 6 BG BQWBWW 4 6 GQBW WWWWQB
output:
3 IMPOSSIBLE
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 39420kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 22ms
memory: 47732kb
input:
13 184 887 WBQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQG QWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQ...
output:
184 114 164 161 118 193 121 204 134 115 33 160 169
result:
wrong answer 2nd lines differ - expected: '372', found: '114'