QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#261247 | #7743. Grand Finale | ucup-team1447 | WA | 53ms | 52904kb | C++14 | 2.3kb | 2023-11-22 19:28:03 | 2023-11-22 19:28:04 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 5005
#define inf 0x3f3f3f3f
int n,m,up,T;
char t[maxn],s[maxn];
int a[maxn];
int f[maxn][maxn];
void work(int O)
{
n=read(),m=read();
cin>>(t+1);
cin>>(s+1);
For(i,1,m){
if(s[i]=='Q')a[i]=1;
if(s[i]=='B')a[i]=2;
if(s[i]=='W')a[i]=0;
}
// memset(f,63,sizeof f);
up=n+m;
For(i,0,up+1) f[m+1][i]=f[m+2][i]=0;
Rep(i,m,1){
For(j,0,up+1){
f[i][j]=inf;
// draw 1
if(j) f[i][j]=min(f[i][j],f[i+1][j-1+(a[i]==1)]-(a[i]==2));
// draw 2
if(i+2>=m) f[i][j]=min(f[i][j],1);
else f[i][j]=min(f[i][j],max(0,f[i+2][j+(a[i]==1)]-(a[i]==2))+1);
f[i][j]=max(f[i][j],0);
// cout<<"i,j "<<i<<" "<<j<<" "<<f[i][j]<<"\n";
}
}
int c1=0,c2=0,res=n;
For(i,1,n){
if(t[i]=='Q')++c1;
if(t[i]=='B')++c2;
}
int pos=1;
// if(O==2 && T==13){
// cout<<n<<" "<<m<<"\n";
// cout<<c1<<" "<<c2<<" "<<"\n";
// For(i,1,m)cout<<a[i];cout<<"\n";
// }
// cout<<"f "<<f[1][c1]<<" "<<c2<<"\n";
if(f[pos][c1]<=c2){
cout<<res<<"\n";
return;
}
auto add=[&](){
c1+=(a[pos]==1);
c2+=(a[pos]==2);
++pos;
if(pos>m){
cout<<res<<"\n";
return 1;
}
return 0;
};
while(1){
++res;
while(c1 && pos<=m){
--c1;
if(add())return;
}
if(!c2){
puts("IMPOSSIBLE");
break;
}
int np=pos,nc1=c1,nc2=c2;
--c2;
if(add())return;
if(add())return;
if(f[pos][c1]<=c2){
cout<<res<<"\n";
return;
}
// pos=np,c1=nc1,c2=nc2;
}
}
signed main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
T=read();
For(_,1,T)work(_);
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3540kb
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: 5444kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 53ms
memory: 52904kb
input:
13 184 887 WBQBBWWBQBQBQBWWBBQQWWQQQBBBQWWWQWBBBBWWWQQBQQQWQBBQQWQQBBWWQWQQBWBQWWWWQWQQWQBWWQQWWQQBWWQWBBBWWQWBQBQWQQWWBQBQQBWQBQBWWBWQWQWBWBQWWQBQQQBWQQWQWWBQBWWQQBQWBQQBQQBQBBQBWBQQWWQBWBBQQBQG QWBQBQBWBQQWWWWQBBBQQQBBBWWWWQWQWWQQQBQBWQQQBWQWQBWWBQQQWQWBQBBQBWBBWBQWQBWWQQBWQQWWQWWQQWBQQWQWBBQBWBQQ...
output:
184 478 558 161 118 720 IMPOSSIBLE 690 297 367 33 160 732
result:
wrong answer 2nd lines differ - expected: '372', found: '478'