Cod sursa(job #3161744)

Utilizator vladsoartavlad sofronea vladsoarta Data 27 octombrie 2023 20:36:05
Problema Reguli Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream cin("reguli.in");
ofstream cout("reguli.out");


vector<long long> pas;
long long preced;

int main()
{long long n;
   cin>>n;
   cin>>preced;

   for(int i=1;i<n;i++)
   {long long curent;
   cin>>curent;
   pas.push_back(curent-preced);

   preced=curent;

   }

   int lps[500005]={0};
       int k=0;
       for(int j=1;j<(int)pas.size();j++)
       {
           while(k!=0&&pas[j]!=pas[k])
            k=lps[k-1];
           if(pas[j]==pas[k])
            k++;
            lps[j]=k;
       }

       int gasit=0;
       int j=pas.size()-1;

       while(j>0&&!gasit)
       {
           if(lps[j])
           {
               long long pos=j;
               long long lungcheck = j-lps[j]+1;

               while(pos-lps[pos]+1==lungcheck&&lps[pos])
               {
                   pos-=lungcheck;

               }
               if(pos+1==lungcheck)
               {cout<<lungcheck<<'\n';
               for(j=0;j<lungcheck;j++)
            cout<<pas[j]<<'\n';
                   gasit=1;
               }

           }
            j--;
       }
       if(!gasit)
        {cout<<pas.size()-1<<'\n';
            for(j=0;j<(int)pas.size();j++)
            cout<<pas[j]<<'\n';

        }



    return 0;
}