Submission #241583

#	Time	Username	Problem	Language	Result	Execution time	Memory
241583		ruler	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	48 ms	19092 KiB

palindromic

// IOI 2021
 
#include <bits/stdc++.h>
using namespace std;

#define sync ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e9, MOD = INF + 7;
 
/////////////////////////////////////////////////////////////////////
 
const int N = 1e6 + 5, BASE = 619;

string s;
int n, h[N], pw[N];

// [l, r)
int hsh(int l, int r) {
	return h[r] - h[l] * pw[r - l];
}

// [l, r]
int solve(int l, int r) {
	int len = r - l + 1;
	for (int i = 1; i <= len; i++) {
		if (l >= r - i + 1) return 1;
		if (hsh(l, l + i) == hsh(r + 1 - i, r + 1)) return 2 + solve(l + i, r - i);
	}
	return 0;
}

void MAIN() {
	cin >> s;
	n = sz(s);
	for(int i = 0; i < n; i++) h[i + 1] = (h[i] * BASE) + ((int) s[i]);
	cout << solve(0, n - 1) << endl;
}

int main() {
 
	sync;

	pw[0] = 1;
	for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * BASE;
	int t = 1; cin >> t;
	while(t--) MAIN();

	return 0;
}

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