Cod sursa(job #1815218)

Utilizator DobosDobos Paul Dobos Data 24 noiembrie 2016 22:29:52
Problema Reguli Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>

#define MMAX 500005
#define BMOD  5000

using namespace std;

typedef long long int var;

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

var V[MMAX],P[MMAX],S[MMAX],e = BMOD - 1;
char buffer[BMOD + 1];

inline void parsare(var &x){
    while(!isdigit(buffer[e])){
        e++;
        if(e == BMOD) fin.read(buffer,BMOD),e = 0;
    }
    x = 0;
    while(isdigit(buffer[e])){
        x = x * 10 + buffer[e] - '0';
        e++;
        if(e == BMOD) fin.read(buffer,BMOD),e = 0;
    }
}


void prefix(var m){
    int q = 0;
    for(int i = 2; i <= m; i++){
        while(q && V[i] != V[q + 1])
            q = P[q];
        if(V[i] == V[q + 1])
            q++;
        P[i] = q;
    }

}

int solve(var p,var m){
    int q = 0,s = 0;
    for(int i = 1; i <= m; i++){
        while(q && V[i] != V[q + 1])
            q = P[q];
        if(V[i] == V[q + 1])
            q++;
        if(q == p){
            q = P[q];
            s++;
            if(s != i / p)
                return 0;
        }
    }
    if(s == m / p){
        for(int i  = m - m % p + 1,q = 1; i <= m; i++,q++)
            if(V[q] != V[i])
                return 0;
            return 1;
    }
    return 0;
}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    var m;

    parsare(m);

    for(int i = 1; i <= m ; i++){
        parsare(V[i]);
    }
    m--;
    for(int i = 1; i <= m; i++)
        V[i] = V[i + 1] - V[i];

    for(int i = 1; i <= m; i++){
        prefix(i);
        if(solve(i,m)){
            fout << i << "\n";
            for(int j = 1; j <= i; j++)
                fout << V[j] << "\n";
            i = m + 1;
        }
    }


    return 0;
}