fork download
copy 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define eb emplace_back
  6. #define pii pair <int, int>
  7. #define pli pair <ll, int>
  8. #define fi first
  9. #define se second
  10. #define all(ac) ac.begin(), ac.end()
  11. #define MASK(x) (1LL << x)
  12. #define ub(i, j) ((i >> j) & 1)
  13. #define FBIT(x) (MASK(x) - 1)
  14. #define FLIP(x, y) (FBIT(x) ^ y)
  15. #define ii make_pair
  16.  
  17. const int MX = 1e5 + 1;
  18. int n, H[MX];
  19.  
  20. namespace subfull {
  21.     bool vis[MX];
  22.     bool check(int s1, int s2) {
  23.         int d = H[s2] - H[s1];
  24.         int last = s2;
  25.         memset(vis, 0, sizeof vis);
  26.         vis[s1] = vis[s2] = 1;
  27.  
  28.         int cnt = 0;
  29.         for(int i=s2 + 1;i<=n;i++) {
  30.             if(H[i] - H[last] == d) vis[i] = 1, last = i, cnt++;
  31.             else
  32.             if(H[last] == H[i]) vis[last] = 0, vis[last = i] = 1; 
  33.         }
  34.  
  35.         if(cnt > n - 2) return 1;
  36.  
  37.         bool flag = 0;
  38.         last = d = -1;
  39.         for(int i=1;i<=n;i++) if(!vis[i]) {
  40.             if(last != -1) {
  41.                 d = H[i] - H[last];
  42.                 last = i;
  43.                 break;
  44.             }
  45.             last = i;
  46.         }
  47.  
  48.         int ed = n + 1;
  49.         for(int i=n;i>=1;i--) {
  50.             if(vis[i]) ed = i;
  51.             else break;
  52.         }
  53.  
  54.         for(int i=last + 1;i<=n;i++) {
  55.             if(flag) vis[i] = 0;
  56.             else
  57.             if(i == ed) break;
  58.  
  59.             if(H[i] - H[last] == d) {
  60.                 if(vis[i]) flag = 1, vis[i] = 0;
  61.                 last = i;
  62.             }
  63.             else
  64.             if(!vis[i]) return 0;
  65.         }
  66.         return 1;
  67.     }
  68.  
  69.     void Output() {
  70.         int cnt = accumulate(vis + 1, vis + n + 1, 0);
  71.         if(cnt == n) vis[n] = 0, cnt--;
  72.         cout << cnt << '\n';
  73.         for(int x=1;x<=n;x++) if(vis[x]) cout << H[x] << ' ';
  74.         cout << '\n' << n - cnt << '\n';
  75.         for(int x=1;x<=n;x++) if(!vis[x]) cout << H[x] << ' ';
  76.         return;
  77.     }
  78.  
  79.     void solve() {
  80.         if(check(1, 2)) Output();
  81.         else
  82.         if(check(1, 3)) Output();
  83.         else
  84.         if(check(2, 3)) Output();
  85.         else cout << -1;
  86.         return;
  87.     }
  88. }
  89.  
  90. int32_t main() {
  91.     ios::sync_with_stdio(false);
  92.     cin.tie(0), cout.tie(0);
  93.     #define task "tet"
  94.     if(fopen(task".inp", "r")) {
  95.         freopen(task".inp", "r", stdin);
  96.         freopen(task".out", "w", stdout);
  97.     }
  98.  
  99.     cin >> n;
  100.     for(int i=1;i<=n;i++) cin >> H[i];
  101.     sort(H + 1, H + n + 1);
  102.  
  103.     subfull::solve();
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10
32 27 24 26 34 18 30 21 15 28
stdout
copy 
5
15 18 21 24 27 
5
26 28 30 32 34
https://ideone.com/sH2DUX
language:
C++ (gcc 8.3)
created:
2 days 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!