Cod sursa(job #929037)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 26 martie 2013 20:09:47
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
#include<string>
using namespace std; 
int n, i, j, k, st, dr, cmax, drm;
int v[2000005];
string s;
long long sol;
 
int main(){
    ifstream fin("pscpld.in");
    ofstream fout("pscpld.out");
    getline(fin,s);
    n=0;
    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;
        }
    
        if(dr>drm)
        {
            v[i]-=2*(dr-drm);
            st+=dr-drm;
            dr=drm;
        }
    
        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;
    }
 
     fout<<sol;
    return 0;
}