Cod sursa(job #881443)

Utilizator vendettaSalajan Razvan vendetta Data 17 februarie 2013 23:00:49
Problema Reguli Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 500005
#define ll long long

int n;
ll a[nmax];
int pi[nmax];

void citeste(){
    f >> n;
    ll x0, x; f >> x0;
    for(int i=1; i<n; ++i){
        f >> x;
        a[i] = x - x0;
        x0 = x;
    }
}

void prefix(){
    pi[1] = 0;
    for(int i=2, q=0; i<n; ++i){
        while(q > 0 && a[q+1] != a[i]) q = pi[q];
        if (a[q+1] == a[i]) ++q;
        pi[i] = q;
    }
}

void rezolva(){
    // acum am vectorul cu ratii trebuie sa determin cel mai mic ciclu
    // avand in vedere ca pot avea si cicluri gen 1 2 2 1 2 2 incerc o solutie gen
    // imi calculez fct prefix de la kmp pe sirul asta; dupa ce o calculez raspunsul o sa fie cel mai mare pi[i] dupa ultimul pi[i] = 0;
    // adica dac ao sa am ceva gen pi[] : 0 0 1 2 0 1 2 3 raspunsul va fi 3 + (poz ultimulului 0 - 3)
    prefix(); int ul = 0; int Rez = 0;
    for(int i=1; i<n; ++i){
        if (pi[i] == 0){
            Rez = 0; ul = i;
            continue;
        }
        Rez = max(Rez, pi[i]);
    }
    Rez += (ul - Rez);
    //cout << Rez << "\n";
    g << n-1 << "\n";
    for(int i=1; i<n; ++i){
        //cout << a[i] << "\n";
        g << a[i] << "\n";
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}