Submission #989069

#	Time	Username	Problem	Language	Result	Execution time	Memory
989069		mraron	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	421 ms	15296 KiB

palindromic

/*
ID: noszaly1
TASK: {TASK}
LANG: C++11               
*/

//Noszály Áron 10o Debreceni Fazekas Mihály Gimnázium

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

int T;

string t;
//using zalgo because I've already solved it with rolling hashes
vector<int> z;
void zalgo(string& str, int l, int r) {
	z.resize(r-l+1);
	int L=0, R=0;
	for(int i=1;i<r-l+1;++i) {
		if(i>R) {
			L=i;R=i;
			while(R<r-l+1 && str[l+R]==str[l+R-L]) R++;
			z[i]=R-L;
			R--;
		}else {
			if(z[i-L]+i<R) {
				z[i]=z[i-L];
			}else {
				L=i;
				while(R<r-l+1 && str[l+R]==str[l+R-L]) R++;
				z[i]=R-L;
				R--;
			}
		}
	}
	
	
}

int limit=1000;
int solve(int L, int R) {
	if(R<L) return 0;
	if(L==R) return 1;
	
	for(int i=1;i<=limit;++i) {
		if(L+i-1>=R-i+1) break;
		
		bool ok=true;
		for(int j=L, k=R-i+1;j<=L+i-1 && k<=R && ok;++j, ++k) {
			ok&=t[j]==t[k];
		}
		
		if(ok) {
			return solve(L+i, R-i)+2;
		}
	}
	

	zalgo(t, L, R);


	for(int i=sz(z)-1;i>=1;--i) {
		if(z[i]+i==sz(z) && z[i]-1<i) {
			return solve(L+z[i], L+i-1)+2;
		}
	}
	
	return 1;
}

int main() {
	IO;
	cin>>T;
	while(T--) {
		cin>>t;
		cout<<solve(0, sz(t)-1)<<"\n";
	}
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40