Submission #245378

#	Time	Username	Problem	Language	Result	Execution time	Memory
245378		tonowak	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	337 ms	20380 KiB

palindromic

#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

struct Hashing {
	vector<int> ha, pw;
	int mod = 1e9 + 696969;
	int base;

	Hashing(string &str, int b = -1) {
		if(b == -1) base = 31;
		else base = b;

		int len = size(str);
		ha.resize(len + 1);
		pw.resize(len + 1, 1);
		REP(i, len) {
			ha[i + 1] = (LL(ha[i]) * base + str[i] - 'a' + 1) % mod;
			pw[i + 1] = (LL(pw[i]) * base) % mod;
		}
	}

	int operator()(int l, int r) {
		return ((ha[r + 1] - LL(ha[l]) * pw[r - l + 1]) % mod + mod) % mod;
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t --> 0) {
		string s;
		cin >> s;
		const int n = size(s);
		Hashing hash(s);

		int answer = 0;
		int L = 0, R = n - 1;
		while(L < R) {
			debug(L, R);
			bool found = false;
			FOR(len, 1, (R - L + 1) / 2)
				if(hash(L, L + len - 1) == hash(R - len + 1, R)) {
					L += len;
					R -= len;
					answer += 2;
					found = true;
					break;
				}
			if(not found)
				break;
		}
		if(L <= R)
			answer += 1;
		cout << answer << '\n';
	}
}

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