제출 #406571

#제출 시각아이디문제언어결과실행 시간메모리
406571Pichon5Palindromic Partitions (CEOI17_palindromic)C++17
100 / 100
339 ms26808 KiB
#include<bits/stdc++.h> #define lcm(a,b) (a/__gcd(a,b))*b #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long int #define vi vector<int> #define vll vector<ll> #define pb push_back #define F first #define S second //"\n" //algoritmo para calcular la cantidad de substrings diferentes using namespace std; const ll MOD=1e9+9; const ll p=131; const int N=1e6+5; ll P[N]; ll h[N]; int main() { //freopen("palindromic.0.02.in","r",stdin); int t; string s; cin>>t; while(t--){ cin>>s; ll n=s.size(); h[0]=0; ll pot=1; for(int i=0;i<n;i++){ ll x=s[i]-'a'+1; P[i]=pot; h[i+1]=(h[i]+x*pot)%MOD; pot=(pot*p)%MOD; } int tam=1; int izq=0,der=n-1; int res=0; while(1){ if(izq+tam-1>=der-tam+1){ res++; break; } ll a=(h[izq+tam]-h[izq]+MOD)%MOD; a=(a*P[n-izq-1])%MOD; ll b=(h[der+1]-h[der-tam+1]+MOD)%MOD; b=(b*P[(n-1)-(der-tam+1)])%MOD; if(a==b){ if(izq+tam==der-tam+1){ res+=2; break; } izq+=tam; der-=tam; tam=1; res+=2; }else{ tam++; } } cout<<res<<endl; } return 0; } //https://codeforces.com/contest/911/problem/D //https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1021 //freopen("palindromic.3.00.in","r",stdin);
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...