Submission #66500

#	Time	Username	Problem	Language	Result	Execution time	Memory
66500		IOrtroiii	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	168 ms	36696 KiB

palindromic

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

const int N = 1e6 + 5;
const int mod = 1e9 + 9277;

string s;
int pw[N], hs[N];

int get(int l,int r) {
	int ret = hs[r] - 1ll * hs[l - 1] * pw[r - l + 1] % mod;
	if (ret < 0) ret += mod; return ret;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	int t; cin >> t;
	while (t--) {
		cin >> s; int n = s.size(); s = '~' + s;
		hs[0] = 0, pw[0] = 1;
		for (int i = 1; i <= n; ++i) {
			hs[i] = (1ll * hs[i - 1] * 43 % mod + (s[i] - 'a' + 1));
			if (hs[i] >= mod) hs[i] -= mod;
			pw[i] = 1ll * pw[i - 1] * 43 % mod;
		}
		cout << solve(1, n) << '\n';
	}
}

Compilation message (stderr)

palindromic.cpp: In function 'int get(int, int)':
palindromic.cpp:12:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (ret < 0) ret += mod; return ret;
  ^~
palindromic.cpp:12:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (ret < 0) ret += mod; return ret;
                           ^~~~~~

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