QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#761373#9565. Birthday GiftMeowmeowmeow#WA 6ms9924kbC++142.9kb2024-11-18 22:27:002024-11-18 22:27:02

Judging History

你现在查看的是最新测评结果

  • [2024-11-18 22:27:02]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:9924kb
  • [2024-11-18 22:27:00]
  • 提交

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
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7880kb

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: 9924kb

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'