Submission #1066115

#TimeUsernameProblemLanguageResultExecution timeMemory
1066115aufanPalindromic Partitions (CEOI17_palindromic)C++17
100 / 100
221 ms27872 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; const int key = 29; const int mod = 1e9 + 9; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t --> 0) { string s; cin >> s; int n = (int)s.size(); vector<int> pr(n + 1); for (int i = 0; i < n; i++) { pr[i + 1] = (pr[i] * key + (s[i] - 'a')) % mod; } vector<int> pw(n + 1); pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = (pw[i - 1] * key) % mod; auto get = [&](int lf, int rg) { return (pr[rg] - pr[lf - 1] * pw[rg - lf + 1] % mod + mod) % mod; }; int ans = 0; for (int i = 1, j = 0; i <= n; i++) { if (get(j + 1, i) == get(n - i + 1, n - j)) { ans += 1; j = i; } } cout << ans << '\n'; } 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...