Submission #1095043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095043		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	184 ms	24472 KiB

palindromic

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int base = 31;
const int MOD = 1000000003;
const int maxn = 1000111;

using namespace std;

int POW[maxn], Hash[maxn], len;
string s;

int getHash(int i,int j) {
    return (Hash[j] - Hash[i - 1] * POW[j - i + 1] + MOD * MOD) % MOD;
}

void solve(){
	cin >> s;
	int n = s.size();
	s = ' ' + s;
    for (int i = 1; i <= n; i++)
        Hash[i] = (Hash[i - 1] * base + s[i] - 'a' + 1) % MOD;
	
	int l1 = 1, r1 = 1, l2 = n, r2 = n;
	int ans = 0;
	while(r1 <= r2){
		if(getHash(l1, r1) == getHash(l2, r2)){
			if(r1 < l2){
				ans += 2;
				l1 = r1 + 1;
				r1++;
				r2 = l2 - 1;
				l2--;
			} else {
				ans++;
				break;
			}
		} else {
			r1++;
			l2--;
		}
	}
	cout << ans << '\n';
}
main() {
    POW[0] = 1;
    for (int i = 1; i <= 1000000; i++)
        POW[i] = (POW[i - 1] * base) % MOD;

	int test; cin >> test;
	while(test--){
		solve();
	}
}

Compilation message (stderr)

palindromic.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~

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