Submission #942171

#TimeUsernameProblemLanguageResultExecution timeMemory
942171vjudge1Palindromic Partitions (CEOI17_palindromic)C++17
100 / 100
110 ms26272 KiB
#include <bits/stdc++.h> #define endl "\n" #define int long long using namespace std; int q, n, P = 47, cnt = 1; const int N = 1000005, M = 1000000007; int p[N], h[N]; string s; bool check_equal(int a, int b, int l) { int ha = (h[a + l] - h[a] + M) % M; int hb = (h[b + l] - h[b] + M) % M; return ha * p[b - a] % M == hb; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> q; p[0] = 1; for (int i = 1; i < N; i++) { p[i] = p[i - 1] * P % M; } while(q--) { cin >> s; cnt = 1; n = s.size(); h[0] = 0; for (int i = 1; i <= n; i++) { h[i] = (h[i-1] + (1LL * (s[i-1] - 'a' + 1) * p[i - 1] % M)) % M; } int l = 0, r = n, k = 1; while(l < r && l + k <= r - k) { if(check_equal(l, r - k, k)) { cnt++; if (l + k != r-k)cnt++; l += k; r -= k; k = 1; } else k++; } cout << cnt << endl; memset(h, 0, sizeof(h)); } return 0; } /* * Before implementing the problem: Do I understand the problem correctly? Which places are tricky? What do I need to remember to implement them correctly? Which place is the heaviest by implementation? Can I do it simpler? Which place is the slowest? Where do I need to be careful about constant factors and where I can choose slower but simpler implementation? ---------------------------------- If not AC: Did you remember to do everything to handle the tricky places you thought about before? Is the solution correct? Do I understand the problem correctly? ---------------------------------- If you have a test on which the solution gives wrong answer: Is the solution doing what it was supposed to do? Is the problem in the code or in the idea? */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...