Submission #366684

#	Time	Username	Problem	Language	Result	Execution time	Memory
366684		penguinhacker	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	448 ms	36104 KiB

palindromic

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

#define ll long long
#define ar array

const int MOD = 1e9 + 7;

namespace Hashing {

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> BDIST(0.1 * MOD, 0.9 * MOD);
const ar<int, 2> base = {BDIST(rng), BDIST(rng)};

ar<int, 2> operator+ (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		if ((a[i] += b[i]) >= MOD)
			a[i] -= MOD;
	return a;
}
ar<int, 2> operator- (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		if ((a[i] -= b[i]) < 0)
			a[i] += MOD;
	return a;
}
ar<int, 2> operator* (ar<int, 2> a, ar<int, 2> b) {
	for (int i = 0; i < 2; ++i)
		a[i] = (ll)a[i] * b[i] % MOD;
	return a;
}
ar<int, 2> make_hash(char c) {
	return {c, c};
}

vector<ar<int, 2>> pows = {{1, 1}};
void extend(int len) {
	while(pows.size() <= len)
		pows.push_back(base * pows.back());
}

struct hstring {
	string s;
	vector<ar<int, 2>> pre = {{0, 0}};
	void add(string t) {
		s += t;
		for (char c : t)
			pre.push_back(base * pre.back() + make_hash(c));
	}
	ar<int, 2> hash(int l, int r) {
		assert(0 <= l && l <= r && r < s.size());
		int len = r - l + 1;
		extend(len);
		return pre[r + 1] - pows[len] * pre[l];
	}
};

}
using namespace Hashing;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t; cin >> t;
	while(t--) {
		string s; cin >> s;
		int n = s.size();
		hstring hs; hs.add(s);
		int last = 0;
		int ans = 0;
		for (int i = 0; i < n / 2; ++i) {
			if (hs.hash(last, i) == hs.hash(n - i - 1, n - last - 1)) {
				last = i + 1;
				ans += 2;
			}
		}
		ans += 2 * last < n;
		cout << ans << "\n";
	}
	return 0;
}

Compilation message (stderr)

palindromic.cpp: In function 'void Hashing::extend(int)':
palindromic.cpp:38:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |  while(pows.size() <= len)
      |        ~~~~~~~~~~~~^~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from palindromic.cpp:1:
palindromic.cpp: In member function 'std::array<int, 2> Hashing::hstring::hash(int, int)':
palindromic.cpp:51:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   assert(0 <= l && l <= r && r < s.size());
      |                              ~~^~~~~~~~~~

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