oj.uz

Submission #161949

# Submission time Handle Problem Language Result Execution time Memory
161949 2019-11-05T11:28:12 Z shayan_p Palindromic Partitions (CEOI17_palindromic) C++14
100 / 100
 258 ms 20872 KB 
// Remember...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=2e6+10,mod=1e9+7;
const ll inf=1e18;

int f[maxn];
char ss[maxn], s[maxn];

int main(){
    int q; cin>>q;
    getchar();
    while(q--){
	int N=0;
	do{
	    ss[N++]=getchar();
	}while(ss[N-1]!='\n');
	ss[--N]='\0';
	int n=0;
	for(int i=0;i<=N-1-i;i++){
	    if(i==N-1-i) s[n++]=ss[i];
	    else s[n++]=ss[i], s[n++]='+', s[n++]=ss[N-1-i], s[n++]='+';
	}
	if(s[n-1] =='+') --n;
	
	int L=-1,R=-1;
	for(int i=0;i<n;i++){
	    if(R<i){
		L=R=i;
		while(L>0 && R<n-1 && s[L-1]==s[R+1]) L--,R++;
		f[i]=R-i;
	    }
	    else{
		if(i + f[L+R-i] >= R){
		    f[i]= R-i;
		    L=i-f[i];
		    while(L>0 && R<n-1 && s[L-1]==s[R+1]) L--,R++;
		    f[i]=R-i;
		}
		else{
		    f[i]= f[L+R-i];
		}		
	    }
	}
	int ans=0;
	int nw=0;
	while(nw<n){
	    int pt=nw+2;
	    while(pt<n && 2*f[(nw+pt)>>1]<pt-nw) pt+=4;
	    if(pt<n){
		ans+=2;
		nw=pt+2;
	    }
	    else{
		ans++;
		break;
	    }
	}
	cout<<ans<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 5 ms 508 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 9 ms 376 KB Output is correct
10 Correct 5 ms 508 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 4 ms 504 KB Output is correct
14 Correct 258 ms 20872 KB Output is correct
15 Correct 141 ms 16376 KB Output is correct
16 Correct 219 ms 20300 KB Output is correct
17 Correct 126 ms 11356 KB Output is correct