Cod sursa(job #492612)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 15 octombrie 2010 12:39:09
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>

using namespace std;

#define maxn 1000100

int n, i, j, k, st, dr, cmax, drm;
int v[2*maxn];
char s[maxn];
long long sol;

int main()
{
    freopen("pscpld.in", "r", stdin);
    freopen("pscpld.out", "w", stdout);
    scanf("%s", s+1);
    n=1;
    while(s[n]!=0)
        ++n;
    --n;
    cmax=1;
    drm=1;
    for(int i=1; i<2*n; i+=2)
        v[i]=1;
    for(int i=1; i<2*n; ++i)
    {
        if(drm>=i/2+i%2)
            v[i]=v[2*cmax-i];
        if(i%2)
        {
            dr=i/2+1+v[i]/2;
            st=i/2+1-v[i]/2;
        }
        else
        {
            dr=i/2+v[i]/2;
            st=i/2-v[i]/2+1;
        }
     //   printf("%d %d\n", st, dr);
        if(dr>drm)
        {
            v[i]-=2*(dr-drm);
            st+=dr-drm;
            dr=drm;
        }
    //    printf("%d %d\n\n", st, dr);
        while(s[st-1]==s[dr+1] && st>1 && dr<n)
        {
            v[i]+=2;
            dr++;
            st--;
        }
        if(dr>drm)
        {
            cmax=i;
            drm=dr;
        }
        if(i%2)
            sol=sol+v[i]/2+1;
        else
            sol=sol+v[i]/2;
       // printf("%d ", v[i]);
    }
  //  printf("\n");
    printf("%lld\n", sol);
    return 0;
}