Submission #563250

#TimeUsernameProblemLanguageResultExecution timeMemory
563250kawaiiPalindromic Partitions (CEOI17_palindromic)C++14
100 / 100
1284 ms20776 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define hash hsh int t, n, m, k, hash[1000005], base = 353, mod = 696969601; string s; mt19937_64 rng; int mul(int x, int y){ if(y == 0) return 1; int ans = mul(x, y / 2); if(y % 2 == 0) return (ans * ans) % mod; else return (((ans * ans) % mod) * x) % mod; } void solve(){ n = s.size(); s = '0' + s; for(int i = 1; i <= n; i++) hash[i] = (hash[i - 1] * base + s[i]) % mod; int cnt = 1, ans = 0; while(cnt <= n - cnt + 1){ int f = cnt; bool flag = 0; while(1){ int num1 = (hash[cnt] - (hash[f - 1] * mul(base, cnt - f + 1)) % mod) % mod; int num2 = (hash[n - f + 1] - (hash[n - cnt] * mul(base, cnt - f + 1)) % mod) % mod; // cout << cnt <<" "<< n - cnt + 1 <<" "<< num1 <<" "<< num2 <<" "<< ans << endl; if((num1 + mod) % mod == (num2 + mod) % mod){ if(cnt == n - cnt + 1) ans++; else ans += 2; cnt++; flag = 1; break; } cnt++; if(cnt > n - cnt + 1) break; } if(!flag){ ans++; break; } } cout << ans << "\n"; } signed main(){ ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr); // rng.seed((int)main ^ time(0)); #ifdef Kawaii auto starttime = chrono::high_resolution_clock::now(); #endif cin >> t; while(t--){ cin >> s; solve(); } #ifdef Kawaii auto endtime = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count(); cout << "\n=====" << "\nUsed: " << duration << " ms\n"; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...