Submission #961184

#TimeUsernameProblemLanguageResultExecution timeMemory
961184LucaIliePalindromic Partitions (CEOI17_palindromic)C++17
100 / 100
524 ms26620 KiB
#include <bits/stdc++.h> using namespace std; struct hasher { int mod, b; vector<int> hashh, put; hasher( string s, int _mod, int _b ) { mod = _mod; b = _b; hashh.resize( s.size() + 1 ); put.resize( s.size() + 1 ); put[0] = 1; hashh[0] = 0; for ( int i = 1; i <= s.size(); i++ ) { put[i] = (long long)put[i - 1] * b % mod; hashh[i] = ((long long)hashh[i - 1] * b + s[i - 1] - 'a') % mod; } } int getHash( int l, int r ) { return (hashh[r + 1] - (long long)hashh[l] * put[r - l + 1] % mod + mod) % mod; } }; const int mod1 = 1e9 + 7; const int mod2 = 1e9 + 9; const int b1 = 37; const int b2 = 31; int main() { int t; cin >> t; while ( t-- ) { string s; cin >> s; hasher hash1( s, mod1, b1 ); hasher hash2( s, mod2, b2 ); int l = 0, r = s.size() - 1, cuv = 0; while ( l <= r ) { int i = 1; while ( i <= (r - l + 1) / 2 ) { if ( hash1.getHash( l, l + i - 1 ) == hash1.getHash( r - i + 1, r ) && hash2.getHash( l, l + i - 1 ) == hash2.getHash( r - i + 1, r ) ) break; i++; } if ( i <= (r - l + 1) / 2 ) { l += i; r -= i; cuv += 2; } else { cuv++; break; } } cout << cuv << "\n"; } return 0; }

Compilation message (stderr)

palindromic.cpp: In constructor 'hasher::hasher(std::string, int, int)':
palindromic.cpp:18:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for ( int i = 1; i <= s.size(); i++ ) {
      |                          ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...