Cod sursa(job #2192122)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 4 aprilie 2018 19:58:15
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <cstring>
#define Nmax 3000005

using namespace std;

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

int man[Nmax];
char a[Nmax], x;
long long ans, len;

void read()
{ a[0]='#';
    while ( f >> x )
    {
        a[++len]=x;
        a[++len]='#';
    }
    len--;
}

void manachers()
{
    int mid=1, rgt=1;
    man[1]=1;
     for ( int i = 1 ; i <= len ; i ++ )
     {
         if(i<=rgt)
            man[i]=min(rgt-i, man[2*mid-i]);
          else
           man[i]=1;
         while ( (a[i+man[i]]==a[i-man[i]]) && (i-man[i]>0) && (i+man[i]<=len) )
            man[i]++;

         if ( i+man[i] > rgt )
          {
              mid=i;
              rgt=i+man[i];
          }
          man[i]--;
     }
}

void solve()
{
  for ( int i = 1 ; i <= len ; i ++ )
     {
         man[i]=man[i]/2;
         if(i%2==1)
          ans++;
         ans+=man[i];
     }
     g << ans;
}

int main()
{
    read();
    manachers();
    solve();

    return 0;
}