Cod sursa(job #1013931)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 21 octombrie 2013 22:02:13
Problema DreptPal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <vector>
#define Nmax 1099
#define pb push_back
#define mp make_pair
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

int M,n,N;
vector < int > S,T;
vector < int > P[Nmax];

inline void ReadInput(vector < int > &S)
{
    S.pb(-99);
    for(int i=1;i<=N;++i)
    {
        int x;
        f>>x;
        S.pb(x);
    }
    S.pb(-88);
}
inline void Preprocess(vector < int > S, vector < int > &T)
{
    //din "1234" fac "-99 -1 1 -1 2 -1 3 -1 4 - 88"
    T.pb(-99);T.pb(-1);
    for(int i=1;i<=N;++i)
    {
        T.pb(S[i]);T.pb(-1);
    }
    T.pb(-88);
    N*=2;
}

inline int FindLPS(vector < int > T, vector < int > &P)
{
    int C=0,R=0;
    P.clear();
    P.resize(P.size()+N+5);
    for(int i=1;i<=N;++i)
    {
        int i_mirror=2*C-i;
        if(R>i)P[i]=min(R-i,P[i_mirror]);
            else P[i]=0;
        while(T[i+1+P[i]] == T[i-1-P[i]])++P[i];
        if(i+P[i]>R)
        {
            C=i;
            R=i+P[i];
        }
    }
}

inline void PrintLPS(vector < int > S,vector < int > P)
{
    //for(int i=1;i<=N;++i)g<<P[i]<<' '; g<<'\n';
    //int maxLen=0,centerIndex=0;
    //for(int i=1;i<=N;++i)
        //if(P[i]>maxLen)
        //{
            //maxLen=P[i];
            //centerIndex=i;
        //}
    //////g<<maxLen<<'\n';
    //int st=(centerIndex-1-maxLen)/2;
    //g<<st<<'\n';
    //for(int i=1;i<=maxLen;++i)g<<S[st+i]<<' '; g<<'\n';
}
int main()

{
    f>>M>>n;
    for(int i=1;i<=M;++i)
    {
        N=n; S.clear(); T.clear();
        ReadInput(S);
        Preprocess(S,T);
        FindLPS(T,P[i]);
        PrintLPS(S,P[i]);
    }
    for(int i=1;i<=M;++i,g<<'\n')
        for(int j=1;j<=2*n;++j)if(j%2==0)g<<P[i][j]<<' ';
    f.close();g.close();
    return 0;
}