Submission #977806

#TimeUsernameProblemLanguageResultExecution timeMemory
977806duckindogPalindromic Partitions (CEOI17_palindromic)C++17
0 / 100
3 ms8796 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1'000'000 + 10; int t; using ull = unsigned long long; ull h[N], pw[N]; ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; } int32_t main() { cin.tie(0)->sync_with_stdio(0); pw[0] = 1; for (int i = 1; i <= 1'000'000; ++i) pw[i] = pw[i - 1] * 19937; cin >> t; while (t--) { string s; cin >> s; for (int i = 1; i <= s.size(); ++i) h[i] = h[i - 1] * 19937 + s[i - 1]; int l = 1, r = s.size(); int answer = 0; int len = 0; while (true) { if (l + len >= r - len) { answer += 1; break; } if (get(l, l + len) != get(r - len, r)) len += 1; else { answer += 2; l = l + len + 1; r = r - len - 1; len = 0; } } cout << answer << "\n"; } }

Compilation message (stderr)

palindromic.cpp: In function 'int32_t main()':
palindromic.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 1; i <= s.size(); ++i) h[i] = h[i - 1] * 19937 + s[i - 1];
      |                     ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...