제출 #500288

#제출 시각아이디문제언어결과실행 시간메모리
500288pooyashamsPalindromic Partitions (CEOI17_palindromic)C++14
100 / 100
51 ms15044 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cstring> #include <iomanip> #include <vector> #include <bitset> #include <stack> #include <queue> #include <cmath> #include <set> #include <map> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; const int maxn = 1e6+10; const int base = 541; const int mod = 1e9+7; int kmp[maxn]; int bpw[maxn]; int n; string str; inline void solve() { cin >> str; n = str.size(); int o = 0; int s = 0; int e = n-1; int h1 = str[s++]; int h2 = str[e--]; int l = 1; int mid = n/2 - (1-n%2); for(int i = 0; i < mid; i++) { if(h1 == h2) { o += 2; h1 = str[s++]; h2 = str[e--]; l = 1; } else { h1 = (1ll*h1*base+str[s++]) % mod; h2 = (1ll*bpw[l++]*str[e--]+h2) % mod; } } if(h1 == h2 and n % 2 == 0) o += 2; else o += 1; cout << o << endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); bpw[0] = 1; for(int i = 1; i < maxn; i++) bpw[i] = 1ll*bpw[i-1]*base%mod; int 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...