Cod sursa(job #2002214)

Utilizator richieYRichie Yeung richieY Data 19 iulie 2017 00:25:00
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

typedef long long int64;

ifstream fin("reguli.in");
ofstream fout("reguli.out");
int main() {
    int n;
    fin >> n;
    
    vector<int64> v(n-1, 0);
    int64 prev;
    fin >> prev;
    for (int i = 0; i < n-1; i += 1) {
        int64 x;
        fin >> x;
        v[i] = x - prev;
        prev = x;
    }
    
    vector<int> p(n-1, 0);
    p[0] = 0;
    int l = 0;
    int len = 0;
    for (int i = 1; i < n-1; i += 1) {
        while (l > 0 && v[i] != v[l]) l = p[l-1];
        if (v[i] == v[l]) l += 1;
        p[i] = l;
        if (l*2 - 1 == i) {
            len = l;
        }
        
        if (p[i]-1 != p[i-1]) {
            len = 0;
        }
    }
    
    if (len == 0) len = n-1;

    fout << len << '\n';
    for (int i = 0; i < len; i += 1) {
        fout << v[i] << '\n';
    }
    
    return 0;
}