제출 #1217294

#제출 시각아이디문제언어결과실행 시간메모리
1217294kiennguyendinhPalindromic Partitions (CEOI17_palindromic)C++20
100 / 100
131 ms17124 KiB
#include <bits/stdc++.h> using namespace std; int t; string s; long long h[1000001]; vector<char> res; long long base = 31,mod = 1000000007; long long exp0[1000001]; int siz; long long getHash(int l,int r){ long long re; if(l == 0) re = h[r]; else re = (h[r] - h[l - 1] + mod) % mod; re = (re * exp0[1000000 - l])%mod; return re; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); //freopen("censor.in","r",stdin); //freopen("censor.out","w",stdout); exp0[0] = 1; for(int i = 1;i <= 1000000;i++) exp0[i] = (exp0[i - 1] * base) % mod; cin >> t; while(t--){ int res = 0; cin >> s; //cout << s << "\n"; h[0] = (int) s[0] - 'a' + 1; siz = s.size(); for(int i = 1;i < siz;i++){ h[i] = (h[i - 1] + ((int) s[i] - 'a' + 1)*exp0[i])%mod; } int l = 0,r = siz - 1,lastL = 0,lastR = siz - 1; bool en = false; while(l <= r){ if(getHash(lastL,l) == getHash(r,lastR)){ //cout << lastL << " " << l << " " << r << " " << lastR << "\n"; if(l == r) res++; else res += 2; lastL = l + 1; lastR = r - 1; if(lastL > lastR){ en = true; } } l++; r--; } if(!en) res++; cout << res << "\n"; } 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...