Cod sursa(job #2811141)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 1 decembrie 2021 13:10:47
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;
class prs{
private:
    FILE *fin;
    char *buff;
    int sp;
    char read_ch(){
    ++sp;
    if(sp==4096){
        sp=0;
        fread(buff,1,4096,fin);
    }
    return buff[sp];
    }
public:
    prs (const char *name){
    fin=fopen(name,"r");
    buff=new char [4096]();
    sp=4095;
    }
    prs& operator >> (long long int &n){
    char c;
    int signn=1;
    while(!isdigit(c=read_ch()) && c!='-');
    if(c=='-'){
        signn=-1;
        n=0;
    }else n=c-'0';
    while(isdigit(c=read_ch()))
        n=n*10+c-'0';
    n=n*signn;
    return *this;
    }
};
prs fin("reguli.in");
FILE *g=fopen("reguli.out","w");
long long int n,nr,s[500005],a,b;
bool verifica(int k){
for(int i=1;i<n;++i)
    if(s[i]!=s[i+k] && i+k<n)
        return 0;
return 1;
}
inline int solve(){
vector <int> pi(n,0);
int q=0;
int ans=n-1;
pi[1]=0;
--n;
for(int i=2;i<=n;++i){
while(q && s[q+1]!=s[i])
    q=pi[q];
if(s[q+1]==s[i])
    ++q;
pi[i]=q;
}
for(int i=1;i<=n;++i){
    int l=i;
    int r=n%l;
    int c=n/l;
    if(pi[n-r]>0 && (n-r)%(n-r-pi[n-r])==0 && (n-r)/(n-r-pi[n-r]) && verifica(l))
        return l;
}
return ans;
}
int main()
{
    fin>>n;
    fin>>a;
    for(int i=2;i<=n;++i){
        fin>>b;
        s[i-1]=b-a;
        a=b;
    }
    int d=solve();
    if(!verifica(d))
        d=n-1;
    fprintf(g,"%d\n",d);
    for(int i=1;i<=d;++i)
        fprintf(g,"%lld\n",s[i]);
}