QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #522062 | #7743. Grand Finale | liqingyang# | WA | 61ms | 52872kb | C++17 | 1.6kb | 2024-08-16 18:01:28 | 2024-08-16 18:01:28 |
Judging History
answer
#include<iostream>
using namespace std;
inline void Max(int &x,int y)
{
x=x>y?x:y;
}
int T,n,m,Q,B;
char s[5010];
inline bool judge(int k)
{
static int f[5010][5010];
for(int i=1;i<=m;i++)
{
for(int j=0;j<=k;f[i][j++]=-1);
}
if(k==n)
{
f[1][Q]=B;
}
for(int i=1,q=Q,b=B,j=0;i<=m;i++)
{
if(j<k-n-1)
{
if(b)
{
b--,j++;
q+=(s[i]=='Q');
b+=(s[i]=='B');
i++;
q+=(s[i]=='Q');
b+=(s[i]=='B');
continue;
}
if(q)
{
q--;
q+=(s[i]=='Q');
b+=(s[i]=='B');
continue;
}
return 0;
}
if(k>n&&b)
{
if(i+2>m)
{
return 1;
}
f[i+2][q+(s[i]=='Q')+(s[i+1]=='Q')]
=b-1+(s[i]=='B')+(s[i+1]=='B');
}
if(q)
{
q--;
q+=(s[i]=='Q');
b+=(s[i]=='B');
}
else
{
b=0;
}
for(int j=0;j<=k;j++)
{
if(f[i][j]<0)
{
continue;
}
if(j)
{
if(i+1>m)
{
return 1;
}
Max(f[i+1][j-1+(s[i]=='Q')],
f[i][j]+(s[i]=='B'));
}
if(f[i][j])
{
if(i+2>m)
{
return 1;
}
Max(f[i+2][j+(s[i]=='Q')],
f[i][j]-1+(s[i]=='B'));
}
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m>>s+1;
Q=B=0;
for(int i=1;i<=n;i++)
{
Q+=(s[i]=='Q');
B+=(s[i]=='B');
}
cin>>s+1;
int l=n,r=n+(m>>1),ans=0;
while(l<=r)
{
int mid=l+r>>1;
judge(mid)?(r=(ans=mid)-1):(l=mid+1);
}
if(!ans)
{
cout<<"IMPOSSIBLE"<<endl;
continue;
}
cout<<ans<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3672kb
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: 3644kb
input:
2 3 8 QBG BBBWBWWW 3 8 QBG BBBWBWWW
output:
3 3
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 61ms
memory: 52872kb
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: 56ms
memory: 51520kb
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: -100
Wrong Answer
time: 18ms
memory: 28856kb
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 IMPOSSIBLE 30 32 27 IMPOSSIBLE 25...
result:
wrong answer 66th lines differ - expected: '34', found: 'IMPOSSIBLE'