Submission #1226085

#TimeUsernameProblemLanguageResultExecution timeMemory
1226085putuputuPalindromic Partitions (CEOI17_palindromic)C++20
100 / 100
156 ms18984 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e6+5; const int b=911; int ph[N]; int p[N]; void h(string s){ int n=s.size(); ph[0]=s[0]; for(int i=1; i<n; i++){ ph[i]=ph[i-1]*b+s[i]; } } int get(int l, int r){ if(l==0){ return ph[r]; }else{ return ph[r]-ph[l-1]*p[r-l+1]; } } signed main(){ int t; cin >> t; p[0]=1; for(int i=1; i<N; i++){ p[i]=p[i-1]*b; } while(t--){ int ans=0; string s; cin >> s; int n=s.size(); int l=0, r=n-1; h(s); while(l<r){ bool g=false; for(int i=1; l+i-1<r-i+1; i++){ if(get(l, l+i-1)==get(r-i+1, r)){ ans+=2; l+=i; r-=i; g=true; break; } // if(l!=r){ // ans++; // } } if(g==false){ break; } } if(l<=r){ ans++; } cout << ans << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...