yicongli

Gym 101848B

Jan 23rd, 2021
754
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=1e5+7;
  17.  
  18. ll a[N];
  19. map<ll,int>mp;
  20.  
  21. int main(){
  22.     // freopen(".in","r",stdin);
  23.     // freopen(".out","w",stdout);
  24.     int n;r(n);
  25.     for(int i=1;i<=n;++i){
  26.         r(a[i]);
  27.     }
  28.     if(n<=15){
  29.         for(int i=1;i<=n;++i){
  30.             for(int j=i+1;j<=n;++j){
  31.                 if((a[j]-a[i])%(j-i))continue;
  32.                 else {
  33.                     ll d=(a[j]-a[i])%(j-i);
  34.                     int cnt=0;
  35.                     for(int k=1;k<=n;++k){
  36.                         cnt+=(a[k]!=a[i]+d*(k-i));
  37.                     }
  38.                     if(cnt<=3){
  39.                         for(int k=1;k<=n;++k){
  40.                             printf("%lld ",a[i]+d*(k-i));
  41.                         }
  42.                         puts("");
  43.                         return 0;
  44.                     }
  45.                 }
  46.             }
  47.         }
  48.     }
  49.     for(int i=1;i<n;++i){
  50.         mp[a[i+1]-a[i]]++;
  51.     }
  52.     int mx=0;
  53.     ll d;
  54.     for(map<ll,int>::iterator it=mp.begin();it!=mp.end();it++){
  55.         if(mx<it->second){
  56.             mx=it->second;
  57.             d=it->first;
  58.         }
  59.     }
  60.     for(int i=1;i<n;++i){
  61.         if(a[i+1]-a[i]==d){
  62.             int cnt=0;
  63.             for(int k=1;k<=n;++k){
  64.                 cnt+=(a[k]!=a[i]+d*(k-i));
  65.             }
  66.             if(cnt<=3){
  67.                 for(int k=1;k<=n;++k){
  68.                     printf("%lld ",a[i]+d*(k-i));
  69.                 }
  70.                 puts("");
  71.                 return 0;
  72.             }
  73.         }
  74.     }
  75.     return 0;
  76. }
RAW Paste Data