Cod sursa(job #1741563)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 14 august 2016 13:15:37
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#define MAXN 500000
long long v[MAXN+1];
int pi[MAXN+1];
int next[MAXN+1];
inline void Calc_Prefix(long long *v,int n){
   int i,k;
   k=0;
   pi[1]=0;
   for(i=2;i<=n;i++){
       while(k>0&&v[k+1]!=v[i])
         k=pi[k];
       if(k<n&&v[k+1]==v[i])
         k++;
       pi[i]=k;
   }
}
int main(){
   FILE*fi,*fout;
   int n,i,j,x,rez;
   long long a,b;
   fi=fopen("reguli.in" ,"r");
   fout=fopen("reguli.out" ,"w");
   fscanf(fi,"%d %lld " ,&n,&a);
   for(i=2;i<=n;i++){
       fscanf(fi,"%lld " ,&b);
       v[i-1]=b-a;
       a=b;
   }
   n--;
   Calc_Prefix(v,n);
   rez=0;
   i=2;
   while(i<=n){
     if(pi[i]*2==i){
       x=pi[i];
       j=i;
       while(j<=n&&pi[j]==x){
           j++;
           x++;
       }
       if(j==n+1)
         rez=i/2;
       i=j;
     }
     else
        i++;
   }
   if(rez==0)
     rez=n;
   fprintf(fout,"%d\n" ,rez);
   for(i=1;i<=rez;i++)
     fprintf(fout,"%lld\n" ,v[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}