제출 #698513

#제출 시각아이디문제언어결과실행 시간메모리
698513dattranxxxPalindromic Partitions (CEOI17_palindromic)C++11
100 / 100
68 ms19420 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int M = 1e9 + 7; struct Hash { int x; Hash(int x = 0): x(x) {} friend Hash operator + (Hash u, const Hash& v) { u.x += v.x; if (u.x >= M) u.x -= M; return u; } friend Hash operator - (Hash u, const Hash& v) { u.x -= v.x; if (u.x < 0) u.x += M; return u; } friend Hash operator * (Hash u, const Hash& v) { u.x = 1LL * u.x * v.x % M; return u; } friend bool operator == (const Hash& u, const Hash& v) { return u.x == v.x; } }; using ull = unsigned long long; const int N = 1e6 + 5; string s; ull h[N], pw[N], base = 31; ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; } int n; int main() { cin.tie(0)->sync_with_stdio(0); cout.tie(0); pw[0] = 1; for (int i = 1; i < N; ++i) { pw[i] = pw[i - 1] * base; } int T; cin >> T; while (T--) { cin >> s; n = s.size(); s = ' ' + s; for (int i = 1; i <= n; ++i) { h[i] = h[i - 1] * base + s[i] - 'a' + 1; } int last = 1, res = 0; for (int i = 1; i <= n / 2; ++i) { if (get(last, i) == get(n - i + 1, n - last + 1)) { res += 2; last = i + 1; } } if (last <= (n + 1) / 2) { res += 1; } cout << res << '\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...