Submission #106849

#TimeUsernameProblemLanguageResultExecution timeMemory
106849FrankenweenPalindromic Partitions (CEOI17_palindromic)C++17
0 / 100
3 ms384 KiB
#ifdef LOCAL #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #define ull unsigned long long #define pll pair<ll, ll> #define mp make_pair #define ll long long #define pb push_back #define deb(x) cout << #x << " = " << x << endl #define all(x) x.begin(), x.end() #define ld long double const ll mod = (ll)1e9 + 7; const ll BASE = 47; const ll inf = (ll)1e18; const long double e = 2.718281828459; const long double pi = 3.141592653; const ld EPS = 1e-9; using namespace std; template <class T> istream& operator>>(istream &in, vector<T> &arr) { for (T &cnt : arr) { in >> cnt; } return in; }; void solve() { string s; cin >> s; ll n = s.size(); ll cnt_pow = 1; ll h1 = 0, h2 = 0; ll answer = 0; for (int i = 0; i < n / 2; i++) { h1 += (ll)(s[i] - 'a' + 1) * cnt_pow; h2 *= BASE; h1 %= mod; h2 += s[n - i - 1] - 'a' + 1; h2 %= mod; cnt_pow *= BASE; cnt_pow %= mod; if (h1 == h2) { answer += 2; h1 = 0; h2 = 0; cnt_pow = 1; } if (i + 1 == n / 2) { if (h1 != h2 or n % 2 == 1) { answer++; } } } cout << answer << "\n"; } int main() { #ifndef LOCAL ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #else freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif cout.precision(30); ll seed = time(0); //cerr << "Seed: " << seed << "\n"; srand(seed); ll t; cin >> t; while (t--) solve(); 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...