QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #764128 | #9565. Birthday Gift | Dixiky_215 | WA | 7ms | 5920kb | C++20 | 2.6kb | 2024-11-20 00:47:48 | 2024-11-20 00:47:57 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e6+7;
int t;
int n;
int dp1[MAXN][2];
int dp2[MAXN][2];
string a;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
cin>>a;
n=a.size();
a=' '+a;
for(int i=0;i<=n;i++)
{
dp1[i][0]=dp1[i][1]=-1e9;
dp2[i][0]=dp2[i][1]=1e9;
}
dp1[0][0]=dp1[0][1]=0;
dp2[0][0]=dp2[0][1]=0;
if(a[1]=='1') dp1[1][1]=dp2[1][1]=1;
else if(a[1]=='0') dp1[1][0]=dp2[1][0]=1;
else
{
dp1[1][1]=dp2[1][1]=1;
dp1[1][0]=dp2[1][0]=1;
}
for(int i=2;i<=n;i++)
{
if(a[i-1]=='2'||a[i]==a[i-1]||a[i]=='2')
{
dp1[i][0]=max(dp1[i][0],dp1[i-2][0]);
dp1[i][1]=max(dp1[i][1],dp1[i-2][1]);
dp2[i][0]=min(dp2[i][0],dp2[i-2][0]);
dp2[i][1]=min(dp2[i][1],dp2[i-2][1]);
}
if(a[i]=='2')
{
if(dp1[i-1][1]>0) dp1[i][0]=max(dp1[i][0],dp1[i-1][1]-1);
if(dp1[i-1][1]>0&&dp1[i-1][1]>=-1e6) dp2[i][0]=min(dp2[i][0],dp1[i-1][1]-1);
if(dp2[i-1][1]>0) dp2[i][0]=min(dp2[i][0],dp2[i-1][1]-1);
dp1[i][1]=max(dp1[i][1],dp1[i-1][0]+1);
dp2[i][1]=min(dp2[i][1],dp2[i-1][0]+1);
if(dp1[i-1][0]>0) dp1[i][1]=max(dp1[i][1],dp1[i-1][0]-1);
if(dp1[i-1][0]>0&&dp1[i-1][0]>=-1e6) dp2[i][1]=min(dp2[i][1],dp1[i-1][0]-1);
if(dp2[i-1][0]>0) dp2[i][1]=min(dp2[i][1],dp2[i-1][0]-1);
dp1[i][0]=max(dp1[i][0],dp1[i-1][1]+1);
dp2[i][0]=min(dp2[i][0],dp2[i-1][1]+1);
}
else if(a[i]=='1')
{
if(dp1[i-1][1]>0) dp1[i][0]=max(dp1[i][0],dp1[i-1][1]-1);
if(dp1[i-1][1]>0&&dp1[i-1][1]>=-1e6) dp2[i][0]=min(dp2[i][0],dp1[i-1][1]-1);
if(dp2[i-1][1]>0) dp2[i][0]=min(dp2[i][0],dp2[i-1][1]-1);
dp1[i][1]=max(dp1[i][1],dp1[i-1][0]+1);
dp2[i][1]=min(dp2[i][1],dp2[i-1][0]+1);
}
else
{
if(dp1[i-1][0]>0) dp1[i][1]=max(dp1[i][1],dp1[i-1][0]-1);
if(dp1[i-1][0]>0&&dp1[i-1][0]>=-1e6) dp2[i][1]=min(dp2[i][1],dp1[i-1][0]-1);
if(dp2[i-1][0]>0) dp2[i][1]=min(dp2[i][1],dp2[i-1][0]-1);
dp1[i][0]=max(dp1[i][0],dp1[i-1][1]+1);
dp2[i][0]=min(dp2[i][0],dp2[i-1][1]+1);
}
if(dp2[i][0]==0) dp1[i][0]=max(dp1[i][0],0);
if(dp2[i][1]==0) dp1[i][1]=max(dp1[i][1],0);
if(dp1[i][0]==0) dp2[i][0]=0;
if(dp1[i][1]==0) dp2[i][1]=0;
}
// for(int i=1;i<=n;i++) cerr<<i<<" "<<dp2[i][0]<<" "<<dp1[i][0]<<" "<<dp2[i][1]<<" "<<dp1[i][1]<<" sad"<<endl;
int ans=n;
for(int i=1;i<=n;i++)
{
int s2=min(dp2[i][0],dp2[i][1]);
ans=min(ans,n-i+s2);
}
cout<<ans<<'\n';
}
return 0;
}
/*
1
0120120101
2
1
0210012101
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5920kb
input:
5 0110101 01020102 0000021111 1012121010 0100202010
output:
3 4 0 6 0
result:
ok 5 number(s): "3 4 0 6 0"
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 5544kb
input:
50000 1010110101 1010101010 0101010101 0101010010 0101010010 1010101010 0101001010 1010010010 0100101010 1010101001 1010100101 0101010100 0100101011 0101101010 1011010110 1011010101 1010010101 1010010010 0101010101 0010101010 0101011010 0100101010 1010101010 1010010101 1010101101 1101010101 10100101...
output:
0 10 10 4 4 10 0 4 4 6 2 8 4 2 4 4 2 4 10 8 2 4 10 2 4 8 2 8 8 4 8 4 4 6 4 4 4 6 10 10 2 6 0 10 8 10 0 10 10 10 4 10 8 10 0 8 4 0 8 2 8 0 6 2 8 10 4 10 10 2 10 2 10 8 6 4 2 8 8 0 8 10 8 10 8 10 2 6 10 4 10 8 10 4 10 6 10 10 10 6 6 6 4 10 10 10 2 2 8 10 6 10 10 8 4 10 6 10 2 2 8 2 10 4 6 0 10 4 6 2 1...
result:
wrong answer 13th numbers differ - expected: '2', found: '4'