Cod sursa(job #2538224)

Utilizator theo2003Theodor Negrescu theo2003 Data 4 februarie 2020 16:06:11
Problema Reguli Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <map>
#include <vector>
using namespace std;
#define ll long long
ll l[500000], prefix[500000];
int main(){
    ll n;
    cin>>n;
    int prev_, tmp;
    cin>>prev_;
    n--;
    for(int x = 0;x<n;x++){
        cin>>l[x];
        tmp = l[x];
        l[x] -= prev_;
        prev_ = tmp;
    }
    prefix[0] = 0;
    for(int x = 1, p = 0;x<n;x++){
        if(l[x] == l[p]){
            p++;
            prefix[x] = p;
        }else{
            while(p && (prefix[p] != prefix[x]))
                p = prefix[p - 1];
            if(p)
                p++;
            prefix[x] = p;
        }
    }
    for(int x = 1;x<=n;x++){
        int tmp1 = n/x, tmp2 = n%x;
        if(prefix[n - tmp2 - 1] && ((n - tmp2) / (n - tmp2 - prefix[n - tmp2 - 1]) == tmp1) && !((n - tmp2) % (n - tmp2 - prefix[n - tmp2 - 1]))){
            for(int y = n - tmp2, z  = 0;y<n;y++){
                if(l[y] != l[z]){
                    goto not12;
                }
                z++;
            }
            goto goto12345;
        }
        goto not12;
        goto12345:
        cout<<x<<'\n';
        for(int z = 0;z<x;z++){
            cout<<l[z]<<'\n';
        }
        break;
        not12:continue;
    }
    return 0;
}