Cod sursa(job #856645)

Utilizator toranagahVlad Badelita toranagah Data 16 ianuarie 2013 20:22:46
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <iostream>
using namespace std;

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

typedef long long int64;
const int MAX_N = 500100;

int v[MAX_N];
int prefix[MAX_N];
int N, K;

void read(), solve(), print();
void compute_prefix(int* pattern);

int main() {
    read();
    solve();
    print();
    return 0;
}

void read() {
    fin >> N;
    --N;
    for (int i = 0; i <= N; ++i) {
        fin >> v[i];
    }
}

void solve() {
    for (int i = N; i > 0; --i) {
        v[i] -= v[i-1];
    }
    compute_prefix(v);
    K = N - prefix[N];
}

void compute_prefix(int* pattern) {
    prefix[1] = 0;
    int p = 0;
    for (int i = 2; i <= N; ++i) {
        while (p > 0 && pattern[p+1] != pattern[i]) p = prefix[p];
        if (pattern[p+1] == pattern[i]) ++p;
        prefix[i] = p;
    }
}

void print() {
    fout << K << '\n';
    for (int i = 1; i <= K; ++i) {
        fout << v[i] << '\n';
    }
}