Cod sursa(job #1961870)

Utilizator BugirosRobert Bugiros Data 11 aprilie 2017 13:53:46
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
using namespace std;

const int MAXN = 500005;

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

long long v[MAXN];
int n;

int prefix[MAXN];

void citire()
{
    in >> n;
    for (int i = 1;i <= n;++i)
        in >> v[i];
    for (int i = 1;i < n;++i)
        v[i] = v[i + 1] - v[i];
    --n;
}



void creare_prefix()
{
    int k = 0;
    prefix[1] = 0;
    for (int i = 2;i <= n;++i)
    {
        while(k > 0 && v[k + 1] != v[i])
            k = prefix[k];
        if (v[k + 1] == v[i])
            ++k;
        prefix[i] = k;
    }
}

int l;


//sufix[i] - adevarat daca sufixul de lungime i este si prefix
bool sufix[MAXN];

void calculare_sufix()
{
    for (int k = prefix[n];k != 0;k = prefix[k])
        sufix[k] = true;
}

bool ok()
{
    int c = n / l;
    int r = n % l;
    if (prefix[n - r] == 0)
        return false;
    if ((n - r) % (n - r - prefix[n - r]) != 0)
        return false;
    if ((n - r) / (n - r - prefix[n - r]) != c)
        return false;
    if (!sufix[r])
        return false;
    return true;
}

void prelucrare()
{
    l = 1;
    while(!ok())
        ++l;
}

void afisare()
{
    out << l << '\n';
    for (int i = 1;i <= l;++i)
        out << v[i] << '\n';
}

int main()
{
    citire();
    creare_prefix();
    calculare_sufix();
    prelucrare();
    afisare();
    return 0;
}