Cod sursa(job #3298335)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 28 mai 2025 21:20:14
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
#define N_MAX (int)5e5 + 5

using namespace std;

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

long long x0, x1, v[N_MAX];
int N, pi[N_MAX], idx;

int main() {
    fin >> N >> x0;
    for (int i = 1; i < N; i++) {
        fin >> x1;
        v[i - 1] = x1 - x0;
        x0 = x1;
    }

    pi[0] = 0;
    for (int i = 1; i < N - 1; i++) {
        if (v[i] == v[pi[i - 1]]) {
            pi[i] = pi[i - 1] + 1;
        }
        else {
            idx = pi[i - 1];
            while (idx > 0 && v[i] != v[idx]) {
                idx = pi[idx];
            }
            if (v[i] == v[idx]) {
                idx++;
            }
            pi[i] = idx;
        }
    }

    if (pi[N - 2] == 0) {
        fout << N - 1 << "\n";
        for (int i = 0; i < N - 1; i++) {
            fout << v[i] << "\n";
        }
    }
    else {
        fout << N - 1 - pi[N - 2] << "\n";
        for (int i = 0; i < N - 1 - pi[N - 2]; i++) {
            fout << v[i] << "\n";
        }
    }

    return 0;
}