Cod sursa(job #1561796)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 4 ianuarie 2016 15:52:07
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAX_N = 500000;

int n;
long long V[1 + MAX_N];
long long D[1 + MAX_N];
int PI[1 + MAX_N];
bool equalPrefSuf[1 + MAX_N];

bool testLength(int L) {
    int k = n / L, r = n % L;

    return(PI[n - r] > 0 &&
           (n - r) % (n - r - PI[n - r]) == 0 &&
           (n - r) / (n - r - PI[n - r]) == k &&
           equalPrefSuf[r]);
}

int main() {
    int i, l, q;
    bool allTheSame;

    in >> n >> V[0];
    n--;
    for(i = 1; i <= n; i++) {
        in >> V[i];
        D[i] = V[i] - V[i - 1];
    }

    for(i = 2, allTheSame = true; i <= n; i++) {
        if(D[i] != D[1]) allTheSame = false;
    }
    if(allTheSame) {
        out << "1\n" << V[2] - V[1] << '\n';
        return 0;
    }

    for(i = 2, q = 0; i <= n; i++) {
        while(q > 0 && D[q + 1] != D[i]) q = PI[q];
        if(D[q + 1] == D[i]) q++;
        PI[i] = q;
    }

    for(q = PI[n]; q > 0; q = PI[q]) {
        equalPrefSuf[q] = true;
    }
    for(l = 2; l < n && testLength(l) == false; l++);

    out << l << '\n';
    for(i = 1; i <= l; i++) {
        out << V[i] - V[i - 1] << '\n';
    }

    return 0;
}