Submission #161949

#	Time	Username	Problem	Language	Result	Execution time	Memory
161949		shayan_p	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	258 ms	20872 KiB

palindromic

// 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 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40