Cod sursa(job #1897776)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 1 martie 2017 18:14:10
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.26 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

/**

                                          `-.`'.-'
                                       `-.        .-'.
                                    `-.    -./\.-    .-'
                                        -.  /_|\  .-
                                    `-.   `/____\'   .-'.
                                 `-.    -./.-""-.\.-      '
                                    `-.  /< (()) >\  .-'
                                  -   .`/__`-..-'__\'   .-
                                ,...`-./___|____|___\.-'.,.
                                   ,-'   ,` . . ',   `-,
                                ,-'   ________________  `-,
                                   ,'/____|_____|_____\
                                  / /__|_____|_____|___\
                                 / /|_____|_____|_____|_\
                                ' /____|_____|_____|_____\
                              .' /__|_____|_____|_____|___\
                             ,' /|_____|_____|_____|_____|_\
,,---''--...___...--'''--.. /../____|_____|_____|_____|_____\ ..--```--...___...--``---,,
                           '../__|_____|_____|_____|_____|___\
      \    )              '.:/|_____|_____|_____|_____|_____|_\               (    /
      )\  / )           ,':./____|_____|_____|_____|_____|_____\             ( \  /(
     / / ( (           /:../__|_____|_____|_____|_____|_____|___\             ) ) \ \
    | |   \ \         /.../|_____|_____|_____|_____|_____|_____|_\           / /   | |
 .-.\ \    \ \       '..:/____|_____|_____|_____|_____|_____|_____\         / /    / /.-.
(=  )\ `._.' |       \:./ _  _ ___  ____  ____ _    _ _ _ _ _  _ __\        | `._.' /(  =)
 \ (_)       )        \/                                            \       (       (_) /
  \    `----'          """"""""""""""""""""""""""""""""""""""""""""""        `----'    /
   \   ____\__                                                              __/____   /
    \ (=\     \                                                            /     /-) /
     \_)_\     \                                                         /     /_(_/
          \     \                                                        /     /
           )     )  _                                                _  (     (
          (     (,-' `-..__                                    __..-' `-,)     )
           \_.-''          ``-..____                  ____..-''          ``-._/
            `-._                    ``--...____...--''                    _.-'
                `-.._                                                _..-'
                     `-..__       FORTIS FORTUNA ADIUVAT       __..-'
                           ``-..____                  ____..-''
                                    ``--...____...--''

*/

class parser{
    public:
        parser() {}
        parser(const char *file_name){
            input_file.open(file_name,ios::in | ios::binary);
            input_file.sync_with_stdio(false);
            index&=0;
            input_file.read(buffer,SIZE);}
        inline parser &operator >>(char n[1000010]){
            for (;buffer[index]<'a' or buffer[index]>'z';inc());
            int cursor=0;
            n[cursor++]='*';
            for (;'a'<=buffer[index] and buffer[index]<='z';inc())
                n[cursor++]=buffer[index],
                n[cursor++]='*';
            n[cursor]=0;
            return *this;}
        ~parser(){
            input_file.close();}
    private:
        fstream input_file;
        static const int SIZE=0x400000; ///4MB
        char buffer[SIZE];
        int index;
        inline void inc(){
            if(++index==SIZE)
                index=0,input_file.read(buffer,SIZE);}
};

parser f ("pscpld.in");
ofstream t ("pscpld.out");

int d[2000010];

int main()
{
    char v[2000010];
    int poz=0,l=0;
    f>>v;
    int n=strlen(v),sol=0;
    for (int i=1;i<=n;++i){
        if (i<=l) d[i]=min(l-i,d[2*poz-i]);
        while (0<=i-d[i]-1 and i+d[i]+1<=n and v[i-d[i]-1]==v[i+d[i]+1])
            ++d[i];
        if (i+d[i]>l)
            l=i+d[i],
            poz=i;
        if (d[i])
            sol+=(d[i]/2+(d[i]%2==1));
    }
    t<<sol;
    return 0;
}