Cod sursa(job #2811511)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 2 decembrie 2021 13:35:35
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>
using namespace std;
class reguli{
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:
    reguli(const char *name){
    fin=fopen(name,"r");
    buff=new char [4096]();
    sp=4095;
    }
    reguli& operator >>(long long int  &n){
    char c;
    int signn=1;
    while(!isdigit(c=read_ch()) && c!='-');
    if(c=='-'){
        n=0;
        signn=-1;
    }else n=c-'0';
    while(isdigit(c=read_ch()))
        n=n*10+c-'0';
    n*=signn;
    return *this;
    }
};
FILE *g=fopen("reguli.out","w");
const int nmax=5e5;
long long int n,s[nmax+5],a,b;
bool verifica(int k){
for(int i=1;i+k<=n;++i)
    if(s[i]!=s[i+k])
        return 0;
return 1;
}
static void afis(int first){
fprintf(g,"%d\n",first);
for(int i=1;i<=first;++i)
    fprintf(g,"%lld\n",s[i]);
}
inline int solve(){
vector <int> pi(n+1,0);
pi[1]=0;
int q=0;
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 f=n/l;
    if(pi[n-r] && (n-r)%(n-r-pi[i])==0 && verifica(l)){
        afis(i);
        return 0;
    }
}
afis(n);
return n;
}
int main()
{
    reguli fin("reguli.in");
    fin>>n;
    fin>>a;
    --n;
    for(int i=1;i<=n;++i){
        fin>>b;
        s[i]=b-a;
        a=b;
    }
    solve();
}