Submission #969458

#TimeUsernameProblemLanguageResultExecution timeMemory
969458_callmelucianPalindromic Partitions (CEOI17_palindromic)C++14
100 / 100
112 ms28736 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const ll base = 211; const ll MOD = 1e9 + 21; const int mn = 1e6 + 6; ll pre[mn], basepow[mn]; ll getHash (int l, int r) { return (pre[r] - pre[l - 1] * basepow[r - l + 1] + MOD * MOD) % MOD; } void solve() { string s; cin >> s; int n = s.length(); s = " " + s; for (int i = 1; i <= n; i++) pre[i] = (pre[i - 1] * base + s[i] - 'a' + 1) % MOD; int ans = 0; for (int r = n; n - r + 1 <= r;) { int l = n - r + 1, flg = 0; for (int k = 1; k < r - l + 1; k++) { if (getHash(l, l + k - 1) != getHash(r - k + 1, r)) continue; flg = 1, r -= k, ans += 2; break; } if (!flg) { ans++; break; } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); basepow[0] = 1; for (int i = 1; i < mn; i++) basepow[i] = basepow[i - 1] * base % MOD; int t; cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...