Cod sursa(job #1974735)

Utilizator raulmuresanRaul Muresan raulmuresan Data 28 aprilie 2017 16:48:06
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<vector>
#include<string>
#define modulo 666013

using namespace std;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

const int NMAX = 500005;

int i, n, k, j,contor,st,dr,y,m;
long long int x[NMAX], a[NMAX];
int prefix[NMAX];
vector<int> sol;

void build_prefix()
{
    prefix[1] = 0;
    int k = 0;
    for(int i = 2; i < n; i++)
    {
        while(k > 0 && a[k + 1] != a[i])
        {
            k = prefix[k];
        }
        if(a[k + 1] == a[i])
        {
            k++;
        }
        prefix[i] = k;
    }
    for(i = 1; i < n; i++)
    {
        //fout << prefix[i] << " ";
    }


}

int main()
{
    fin >> n;
    for(i = 1; i <= n; i++)
    {
        fin >> x[i];
    }

    for(i = 1; i < n ; i++)
    {
        a[i] = x[i + 1] - x[i];
        //fout << x[i] << " ";
    }

    for(i = 1; i < n ; i++)
    {
        //fout << a[i] << " ";
    }
    //fout <<"\n";


    build_prefix();
    int k = n - 1 - prefix[n-1];
    fout << k << "\n";
    for(i = 1; i <= k; i++)
    {
        fout << a[i] <<"\n";
    }
    //fout <<n - 1 - prefix[n-1]<<"\n";

//    j=n-1-p[n-1];




}