Submission #1899505
Source Code Expand
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
using namespace std;
#define bll long long
#define dou double
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; ++i)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; --i)
#define Mem(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(b))
const int maxn=1e5+100;
int N;
char s[maxn];
int A[maxn];
int pre[maxn],nex[maxn];
void Prepare()
{
For(i,1,N) A[i]=(s[i]=='1');
A[0]=A[N+1]=-1;
For(i,1,N)
{
pre[i]=(A[i]==A[i-1] ? pre[i-1] : i);
}
Rof(i,N,1)
{
nex[i]=(A[i]==A[i+1] ? nex[i+1] : i);
}
}
bool can_change(int x,int y,int k)
{
if (nex[x]>=k) return 1;
if (N-pre[y]+1>=k) return 1;
return 0;
}
bool check(int k)
{
For(i,1,N-k+1)
{
int j=i+k-1;
if (nex[i]>=j) return 1;
if (can_change(i,j,k)) return 1;
}
return 0;
}
int main()
{
for (; scanf("%s",s+1)!=EOF; )
{
N=strlen(s+1);
Prepare();
int le=0,ri=N+1;
while(le+1<ri)
{
int mid=(le+ri)>>1;
check(mid) ? le=mid : ri=mid;
}
printf("%d\n",le);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Wide Flip |
User |
Out_of_Cage |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
1460 Byte |
Status |
AC |
Exec Time |
4 ms |
Memory |
1536 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, s1.txt, s2.txt, s3.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
4 ms |
1536 KB |
02.txt |
AC |
4 ms |
1536 KB |
03.txt |
AC |
4 ms |
1536 KB |
04.txt |
AC |
4 ms |
1536 KB |
05.txt |
AC |
4 ms |
1536 KB |
06.txt |
AC |
3 ms |
1536 KB |
07.txt |
AC |
2 ms |
1536 KB |
08.txt |
AC |
3 ms |
1536 KB |
09.txt |
AC |
4 ms |
1536 KB |
10.txt |
AC |
4 ms |
1536 KB |
11.txt |
AC |
3 ms |
1536 KB |
12.txt |
AC |
3 ms |
1536 KB |
13.txt |
AC |
3 ms |
1536 KB |
14.txt |
AC |
4 ms |
1536 KB |
15.txt |
AC |
4 ms |
1536 KB |
16.txt |
AC |
3 ms |
1536 KB |
17.txt |
AC |
2 ms |
1536 KB |
18.txt |
AC |
2 ms |
1536 KB |
19.txt |
AC |
2 ms |
1536 KB |
20.txt |
AC |
2 ms |
1536 KB |
21.txt |
AC |
1 ms |
256 KB |
22.txt |
AC |
1 ms |
256 KB |
23.txt |
AC |
1 ms |
256 KB |
24.txt |
AC |
1 ms |
256 KB |
25.txt |
AC |
1 ms |
256 KB |
26.txt |
AC |
1 ms |
256 KB |
27.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |
s3.txt |
AC |
1 ms |
256 KB |