Cod sursa(job #1576828)

Utilizator redcrocodileIlies Andreea redcrocodile Data 22 ianuarie 2016 21:26:57
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream f("pscpld.in");
ofstream g("pscpld.out");

int n,d[2000003],i,mij,dr;
long long nr;
char s[2000003],ronisoara[2000003];

void pali()
{
    mij=1; dr=1;
    for (i=2;i<=n;i++)
    {
        if (i<=dr) d[i]=min(d[2*mij-i],dr-i);
        while(s[i+d[i]+1]==s[i-d[i]-1])
            d[i]++;
        if (i+d[i]>dr)
           {mij=i;
            dr=i+d[i];}
    }
}

int main()
{
    f>>(ronisoara+1);
    n=strlen(ronisoara+1);
    nr=n;
    for (i=1;i<=n;i++)
    { s[2*i-1]='1';
      s[2*i]=ronisoara[i];}
    n=n*2;
    s[0]='2';s[n+1]='3';
    pali();
    for (i=1;i<=n;i++)
        if (i%2==1) nr+=(d[i]+1)/2;
               else nr+=d[i]/2;
    g<<nr;
    return 0;
}