제출 #230646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230646		islingr	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	105 ms	17564 KiB

palindromic

#include <iostream>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)

#define sz(x) int((x).size())

using ll = long long;
constexpr ll p = 5, M = 1e9 + 7, N = 1 << 20;

string s; int n;
ll pp[N], pref[N];

void init() {
	rep(i, 0, n) pref[i + 1] = (pref[i] + pp[i] * (s[i] - 'a' + 1)) % M;
}

ll hsh(int l, int r) { // [l, r]
	int ret = pref[r + 1] - pref[l];
	ret = ret * pp[n - l] % M;
	if (ret < 0) ret += M;
	return ret;
}

int solve() {
	cin >> s; n = sz(s);
	init();
	int cnt = 0;
	int x = 0, y = n - 1;
	bool found;
	while (x <= y) {
		int l = x, r = y;
		found = false;
		while (l < r) {
			if (hsh(x, l) == hsh(r, y)) {
				cnt += 2;
				found = true;
				break;
			}
			++l; --r;
		}
		x = l + 1;
		y = r - 1;
	}
	if (!found) ++cnt;
	return cnt;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	pp[0] = 1;
	rep(i, 1, N) pp[i] = p * pp[i - 1] % M;

	int t; cin >> t;
	while (t--) cout << solve() << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

palindromic.cpp: In function 'int solve()':
palindromic.cpp:46:2: warning: 'found' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (!found) ++cnt;
  ^~

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