fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+1;
  4. int A[N],n,In[N],ok,In2[N];
  5. void Output(){
  6.     int cnt1=0,cnt2=0;
  7.     for(int i=1;i<=n;i++){
  8.         if(In[i]==1)
  9.             cnt1++;
  10.         if(In[i]==2)
  11.             cnt2++;
  12.     }
  13.     if(cnt2==0){
  14.         cnt1--;
  15.         cnt2=1;
  16.         In[n]=2;
  17.     }
  18.     if(cnt1==0){
  19.         cnt1=1;
  20.         cnt2--;
  21.         In[n]=1;
  22.     }
  23.     printf("%d\n",cnt1);
  24.     for(int i=1;i<=n;i++){
  25.         if(In[i]==1)
  26.             printf("%d ",A[i]);
  27.     }
  28.     printf("\n");
  29.     printf("%d\n",cnt2);
  30.     for(int i=1;i<=n;i++){
  31.         if(In[i]==2){
  32.             printf("%d ",A[i]);
  33.         }
  34.     }
  35. }
  36. void reset1(){
  37.     for(int i=1;i<=n;i++){
  38.         if(In[i]==2)
  39.             In[i]=0;
  40.     }
  41. }
  42. bool SimpleCheck(){
  43.     int fir=-1,sec=-1,x,cnt=2;
  44.     for(int i=1;i<=n;i++){
  45.         if(!In[i]){
  46.             if(fir==-1){
  47.                 fir=i;
  48.                 In[fir]=2;
  49.             }
  50.             else{
  51.                 if(sec==-1){
  52.                     sec=i;
  53.                     x=A[sec]-A[fir];
  54.                     In[sec]=2;
  55.                 }
  56.                 else{
  57.                     if(A[i]!=A[fir]+cnt*x){
  58.                         return 0;
  59.                     }
  60.                     else{
  61.                         In[i]=2;
  62.                         cnt++;
  63.                     }
  64.                 }
  65.             }
  66.         }
  67.     }
  68.     return 1;
  69. }
  70. void Solve(int fir,int sec){
  71.     In[fir]=1;
  72.     int x=A[sec]-A[fir],i=sec,cnt=1,l1=fir,l2=-1;      //l1 i l2 are last in first street
  73.     while(i!=n+1){
  74.         if(A[i]==x*cnt+A[fir]){
  75.             In[i]=1;
  76.             cnt++;
  77.             if(l2==-1)
  78.                 l2=i;
  79.             else{
  80.                 l1=l2;
  81.                 l2=i;
  82.             }
  83.         }
  84.         i++;
  85.     }
  86.     if(SimpleCheck()){
  87.         ok=1;
  88.         Output();
  89.         return;
  90.     }
  91.     reset1();
  92.     In[l2]=0;           //last is now in second street
  93.     if(SimpleCheck()){
  94.         ok=1;
  95.         Output();
  96.         return;
  97.     }
  98.     reset1();
  99.  
  100.     int x2=A[l1+1]-A[l1],cnt2=0,f;
  101.     In[l1]=0,In[l2]=0;
  102.     for(int i=1;i<=n;i++){
  103.         if(!In[i]){
  104.             f=i;                // find first in second street
  105.             break;
  106.         }
  107.     }
  108.     for(int i=1;i<=n;i++){
  109.         if(A[i]==A[f]+cnt2*x2){
  110.             In2[i]=2;
  111.             cnt2++;
  112.         }
  113.         else{
  114.             if(i>=l1){           //must fill larger then l1 bc first street won't
  115.                 ok=0;
  116.                 return;
  117.             }
  118.         }
  119.     }
  120.     cnt=0;
  121.     for(int i=1;i<=n;i++){
  122.         if(!In2[i]){
  123.             if(A[i]!=A[fir]+cnt*x){
  124.                 ok=0;
  125.                 return ;
  126.             }
  127.             else{
  128.                 In2[i]=1;
  129.                 cnt++;
  130.             }
  131.         }
  132.     }
  133.     for(int i=1;i<=n;i++){
  134.         In[i]=In2[i];
  135.     }
  136.     Output();
  137.     ok=1;
  138. }
  139. void reset2(){
  140.     for(int i=1;i<=n;i++){
  141.         In[i]=0;
  142.         In2[i]=0;
  143.     }
  144. }
  145. int main()
  146. {
  147.     scanf("%d",&n);
  148.     for(int i=1;i<=n;i++){
  149.         scanf("%d",&A[i]);
  150.     }
  151.     sort(A+1,A+n+1);
  152.     if(n==1){
  153.         printf("1\n");
  154.         printf("%d",A[0]);
  155.         return 0;
  156.     }
  157.     if(n==2){
  158.         printf("1\n");
  159.         printf("%d\n",A[0]);
  160.         printf("1\n");
  161.         printf("%d",A[1]);
  162.         return 0;
  163.     }
  164.     Solve(1,2);
  165.     if(ok)
  166.         return 0;
  167.     reset2();
  168.  
  169.     Solve(1,3);
  170.     if(ok)
  171.         return 0;
  172.     reset2();
  173.  
  174.     Solve(2,3);
  175.     if(ok)
  176.         return 0;
  177.     else
  178.         printf("-1");
  179.     return 0;
  180. }
  181. /*
  182.     8
  183.     1 6 3 8 9 5 5 7
  184.     */
  185.  
Runtime error #stdin #stdout 0s 16416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/h4UaFo
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!