제출 #161936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161936		shayan_p	Palindromic Partitions (CEOI17_palindromic)	C++14	0 / 100	2 ms	376 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];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int q; cin>>q;
    while(q--){
	string ss; cin>>ss;
	string s="";
	for(int i=0;i<=sz(ss)-1-i;i++){
	    if(i==sz(ss)-1-i) s.PB(ss[i]);
	    else s.PB(ss[i]), s.PB('+'), s.PB(ss[sz(ss)-1-i]), s.PB('+');
	}
	if(s.back()=='+') s.pop_back();
	
	int n=sz(s);
	int L=-1,R=-1;
	for(int i=0;i<n;i++){
	    if(i<R){
		L=R=i;
		while(L>0 && R<sz(s)-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<sz(s)-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<sz(s)){
	    int pt=nw+2;
	    while(pt<sz(s) && 2*f[(nw+pt)>>1]<pt-nw) pt+=2;
	    if(pt<sz(s)){
		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: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40