Submission #1276741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276741		herominhsteve	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	94 ms	20060 KiB

palindromic

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "PARPALIND"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x) memset(x,0,sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void timer(){
	const int timelimit= 1000;
	int runtime= 1000*clock()/CLOCKS_PER_SEC; 
    if (runtime>timelimit){
		cerr<<"TLE: "<<runtime<<el;
	}
}

const int base= 257;
const int MAXN=  1e6+1;
long long power[MAXN];

void inHash(string &str, vector<long long> &hashing,int n){
	hashing.resize(n+1,0);
	for (int i=1;i<=n;i++){
		hashing[i]= (hashing[i-1]*base + (str[i-1]-'a'+1))%MOD;
	}
}

long long getHash(int l,int r,vector<long long> &hashing){
	return (hashing[r]-hashing[l-1]*power[r-l+1]%MOD+ 1ll*MOD*MOD)%MOD;
}

void sol(){
	string str;
	cin>>str;
	int n=str.size();
	vector<long long> hashing;
	inHash(str,hashing,n);
	int res=0;
	int l=1;
	for (;l<=n/2;l++){
		int r= n-l+1;
		int i=l;
		int j=r;
		// [l,i] [j,r]
		while (getHash(l,i,hashing)!=getHash(j,r,hashing) and i<=j){
			i++;
			j--;
		}
		if (i>j){
			break;
		}
		res+=2;
		l=i;
	}
	if (l<= (n+1)/2) res++;
	cout<<res<<el;
}

void queries(){
    power[0]=1;
	for (int i=1;i<MAXN;i++) power[i]=power[i-1]*base%MOD;
	int q;
    cin>>q;
    while (q--){
        sol();
    }
}

int main(){
    setup();
    queries();
    timer();
}

Compilation message (stderr)

palindromic.cpp: In function 'void setup()':
palindromic.cpp:13:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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