oj.uz

Submission #226679

# Submission time Handle Problem Language Result Execution time Memory
226679 2020-04-24T18:42:15 Z keta_tsimakuridze Palindromic Partitions (CEOI17_palindromic) C++14
0 / 100
 19 ms 16000 KB 
#include<bits/stdc++.h>
using namespace std;
long long mod,p,t,k,i,pwr[1000005],j,s1,s2,cur,ans,p1,mod1,pwr1[1000005],S1,S2;
string s;
int main(){
	cin>>t;
	p=31;
	p1=29;
	mod=1e9+7;
	mod1=1e9+9;
	pwr[1]=1;
	pwr1[1]=1;
	for(k=2;k<=1000005;k++){
		pwr[k]=pwr[k-1]*p%mod;
		pwr1[k]=pwr1[k-1]*p1%mod1;
	} 
	while(t--){ ans=0;
		cin>>s;
		j=s.size()-1;
        cur=1;s2=s1=S1=S2=0;
		for(i=0;i<j;i++){
			s1+=pwr[cur]*((int)s[i]-'a'+1)%mod;
			S1+=pwr1[cur]*((int)s[i]-'a'+1)%mod1;
			s1%=mod;
			S1%=mod1;
			s2=s2*p%mod+((int)s[j]-'a'+1);
			S2=S2*p1%mod1+((int)s[j]-'a'+1);
			s2%=mod;  
			S2%=mod1;
			if(s1==s2 && S1==S2){
				cur=1; s1=s2=0;  
				ans+=2;  S1=S2=0;
			}else cur++;
			j--;
		}  //cout<<cur<<endl;
		if(cur!=1 || s.size()%2==1) cout<<ans+1<<endl;
		else cout<<ans<<endl;
		ans=0;
	}
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 16000 KB Output isn't correct
2 Halted 0 ms 0 KB -