Cod sursa(job #473494)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 29 iulie 2010 18:45:45
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <fstream>
#include <stdio.h>
using namespace std;
long long suma;
char s[2000000];
typedef struct{
    int c,s;} palindrom;
int pl,n,i,d1,d2,d3,lg[2000000];
int minim(int a,int b,int c)
{
    if((a<b)&&(a<c)) return a;
    if((b<a)&&(b<c)) return b; else return c;
}
palindrom pal[2000000];
int main()
{
    freopen("pscpld.in","r",stdin);
    ofstream fo("pscpld.out");
    while(1) { s[++n]=getchar(); if(s[n]=='\n') break; s[++n]=' '; }
    n-=2;
    for(i=1;i<=n;i++)
    {
    if(s[i]!=' ') lg[i]=1;
    if(pal[i].s)
    {
    if((pal[i].s%2==1)&&(pal[i].c%2==1))
    {
        d1=(pal[i].c/2+1)-(pal[i].s/2+1)+1;
        d2=(pal[i].s/2+1)-(pal[i].c/2+1)+lg[pal[i].c];
        d3=lg[pal[i].s];
        lg[i]=minim(d1,d2,d3);
    }
    if((pal[i].s%2==1)&&(pal[i].c%2==0))
    {
        d1=(pal[i].c/2)-(pal[i].s/2+1)+1;
        d2=(pal[i].s/2+1)-(pal[i].c/2)+lg[pal[i].c];
        d3=lg[pal[i].s];
        lg[i]=minim(d1,d2,d3);
    }
    if((pal[i].s%2==0)&&(pal[i].c%2==1))
    {
        d1=(pal[i].c/2+1)-(pal[i].s/2+1)+1;
        d2=(pal[i].s/2)-(pal[i].c/2+1)+lg[pal[i].c];
        d3=lg[pal[i].s];
        lg[i]=minim(d1,d2,d3);
    }
    if((pal[i].s%2==0)&&(pal[i].c%2==0))
    {
        d1=(pal[i].c/2)-(pal[i].s/2+1)+1;
        d2=(pal[i].s/2)-(pal[i].c/2)+lg[pal[i].c];
        d3=lg[pal[i].s];
        lg[i]=minim(d1,d2,d3);
    }
    }
    if(s[i]!=' '){
                    pl=lg[i]*2;
                    while((i+pl<=n)&&(i-pl>=1))
                    {
                        if(s[i+pl]!=s[i-pl]) break;
                        pal[i+pl-1].s=i-pl+1;
                        pal[i+pl].s=i-pl;
                        pal[i+pl-1].c=i;
                        pal[i+pl].c=i;
                        lg[i]++;
                        pl+=2;
                    }
                 }
    if(s[i]==' '){
                    pl=lg[i]*2+1;
                    while((i+pl<=n)&&(i-pl>=1))
                    {
                        if(s[i+pl]!=s[i-pl]) break;
                        pal[i+pl-1].s=i-pl+1;
                        pal[i+pl].s=i-pl;
                        pal[i+pl-1].c=i;
                        pal[i+pl].c=i;
                        lg[i]++;
                        pl+=2;
                    }

                 }
    suma+=lg[i];
    }
    fo<<suma<<"\n";
    fo.close();
    return 0;
}