Cod sursa(job #3246235)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 2 octombrie 2024 13:54:23
Problema Reguli Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "reguli";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const int NMAX = 5e5 + 5;

int n;

long long x;

long long last;

long long a[NMAX];

int pi[NMAX];

void prefix()
{
    for(int i = 1; i < n; i ++)
    {
        int j = pi[i - 1];

        while(j > 0 && a[j] != a[i])
        {
            j = pi[j - 1];
        }

        if(a[j] == a[i])
        {
            j ++;
        }

        pi[i] = j;
    }
}

int main()
{

    f >> n;

    f >> last;

    for(int i = 1; i < n; i ++)
    {
        f >> x;

        a[i - 1] = x - last;

        last = x;
    }

    n --;

    prefix();

    rest = pi[n - 1];

    n -= pi[n - 1];

    prefix();

    g << n - pi[n - 1] << '\n';

    for(int i = 0; i < n - pi[n - 1]; i ++)
    {
        g << a[i] << '\n';
    }

    return 0;
}