# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
99931 | pavel | Palindromic Partitions (CEOI17_palindromic) | C++14 | 28 ms | 8184 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1000006;
const int MOD = 1000000007;
const int BASE = 34;
int n;
char str[MAXN];
int p[MAXN];
int ADD(ll a, ll b){
return (a+b)%MOD;
}
int MUL(ll a, ll b){
return a*b%MOD;
}
int main(){
p[0]=1;
for(int i=1;i<MAXN;++i) p[i]=MUL(BASE, p[i-1]);
int tcc;
scanf("%d", &tcc);
for(int tc=0;tc<tcc;++tc){
scanf("%s", str);
n=strlen(str);
int ls=0,rs=n-1, le=1, re=n;
int lh=str[0]-'a'+1, rh=str[n-1]-'a'+1;
int sol=0;
while(true){
while(lh!=rh){
lh=ADD(MUL(lh, BASE), str[le]-'a'+1);
++le;
--rs;
rh=ADD(MUL(str[rs]-'a'+1, p[re-rs-1]), rh);
}
if(ls==rs && le==re){
sol++;
break;
}else{
sol+=2;
}
ls=le;le=ls+1;lh=str[ls]-'a'+1;
re=rs;rs=re-1;rh=str[rs]-'a'+1;
}
printf("%d\n", sol);
}
}
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... |