QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #761386 | #9565. Birthday Gift | Meowmeowmeow | WA | 6ms | 7860kb | C++14 | 2.9kb | 2024-11-18 22:32:09 | 2024-11-18 22:32:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500005
#define int long long
int fl[MAXN][3][3];
int fr[MAXN][3][3];
int p[MAXN];
char a[MAXN];
int n;
void mx(int &x,int y) {
if(x < y) x = y;
}
void mn(int &x,int y) {
if(y < 0) y = 0;
if(x > y) x = y;
}
signed main() {
int T;
cin >> T;
while(T --) {
scanf("%s",a+1);
n = strlen(a+1);
for(int i = 0; i <= n+1; i ++) {
fl[i][0][0] = 1e18;
fl[i][0][1] = 1e18;
fl[i][1][0] = 1e18;
fl[i][1][1] = 1e18;
fr[i][0][0] = 0;
fr[i][0][1] = 0;
fr[i][1][0] = 0;
fr[i][1][1] = 0;
p[i] = 0;
fr[i][0][1] = -1;
fr[i][1][1] = -1;
}
p[0] = 1;
for(int i = 1; i <= n; i ++) {
if(a[i] != '1') {
if(p[i-1] == 1) {
fl[i][0][1] = 1;
mx(fr[i][0][1],1);
}
mn(fl[i][1][1],fl[i-1][0][0]-1);
mn(fl[i][1][0],fl[i-1][0][1]-1);
mn(fl[i][0][1],fl[i-1][1][0]+1);
mn(fl[i][0][0],fl[i-1][1][1]+1);
mx(fr[i][1][1],fr[i-1][0][0]-1);
mx(fr[i][1][0],fr[i-1][0][1]-1);
mx(fr[i][0][1],fr[i-1][1][0]+1);
mx(fr[i][0][0],fr[i-1][1][1]+1);
if(fl[i][0][0] == 0 || fl[i][1][0] == 0) p[i] = 1;
}
if(a[i] != '0') {
if(p[i-1] == 1) {
fl[i][1][1] = 1;
mx(fr[i][1][1],1);
}
mn(fl[i][1][1],fl[i-1][0][0]+1);
mn(fl[i][1][0],fl[i-1][0][1]+1);
mn(fl[i][0][1],fl[i-1][1][0]-1);
mn(fl[i][0][0],fl[i-1][1][1]-1);
mx(fr[i][1][1],fr[i-1][0][0]+1);
mx(fr[i][1][0],fr[i-1][0][1]+1);
mx(fr[i][0][1],fr[i-1][1][0]-1);
mx(fr[i][0][0],fr[i-1][1][1]-1);
if(fl[i][0][0] == 0 || fl[i][1][0] == 0) p[i] = 1;
}
if(p[i]) {
if(fr[i][0][0] >= 2) fl[i][0][0] = 2;
else fl[i][0][0] = 1e18;
if(fr[i][1][0] >= 2) fl[i][1][0] = 2;
else fl[i][1][0] = 1e18;
}
/* cout<<i<<" "<<p[i]<<"---\n";
cout<<fl[i][0][0]<<" "<<fl[i][0][1]<<" "<<fl[i][1][0]<<" "<<fl[i][1][1]<<"\n";
cout<<fr[i][0][0]<<" "<<fr[i][0][1]<<" "<<fr[i][1][0]<<" "<<fr[i][1][1]<<"\n";
*/ //if(p[i]) fl[i][0][0] = fl[i][1][0] = 0;
}
if(p[n]) cout<<0<<"\n";
else cout<<min({fl[n][0][0],fl[n][0][1],fl[n][1][0],fl[n][1][1]})<<"\n";
}
}
/*
5
0110101
01020102
0000021111
1012121010
0100202010
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7860kb
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: 6ms
memory: 7828kb
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 2 2 0 4 2 4 10 8 2 4 10 2 4 8 0 8 8 4 8 4 4 6 4 4 4 6 10 10 2 0 0 10 8 10 0 10 10 10 4 10 8 10 0 8 4 0 8 2 8 0 6 2 8 10 2 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 2 10 10 10 2 2 8 10 6 10 10 8 4 10 6 10 2 2 8 2 10 4 6 0 10 2 6 2 1...
result:
wrong answer 27th numbers differ - expected: '2', found: '0'