# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1248102 | nhnguyen14 | Palindromic Partitions (CEOI17_palindromic) | C++17 | 89 ms | 15728 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class X,class Y>
bool minimize(X &x,Y y){
if (x>y) return x=y,true; return false;
}
template<class X,class Y>
bool maximize(X &x,Y y){
if (x<y) return x=y,true; return false;
}
const int N=(int)1e6+1;
const int inf = (int)1e9+7;
int dp[N+2];
int n;
int p[N+2]={} , h[N+2]= {};
const int base = 256;
const int MOD = 1e9+9;
string s;
int Get(int l,int r){
return ((LL)h[r] - (LL)p[r-l+1] * h[l - 1] + (LL)MOD*MOD) % MOD;
}
void solve(){
cin>>s; s = '#' + s;
n = s.size() - 1;
for(int i = 0 ; i <= n + 1; ++i) dp[i] = -inf;
p[0] = 1;
for(int i=1;i<=n;++i) {
p[i] = (LL)p[i-1]*base % MOD;
h[i] = ((LL)h[i-1]*base+s[i]) % MOD;
}
int ans = 0;
int l = 1 , r = 1;
while (r <= n / 2){
if (Get(l,r)==Get(n-r+1,n-l+1)){
ans+=2;
r++;
l=r;
}
else {
++r;
}
}
if (n%2==1 || l!=n/2+1) ++ans;
cout<<ans<<'\n';
return ;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0) ;
#define name "main"
if (fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
int test; cin>>test;
while(test--) solve();
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |