Advertisement
Guest User

Untitled

a guest
Feb 7th, 2016
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5+5;
  6. int a[N], len[N], p[N], last[10*N];
  7. struct comp {
  8.     bool operator()(const int& l, const int& r) const {
  9.         return len[l] == len[r] ? l < r : len[l] > len[r];
  10.     }
  11. };
  12.  
  13. void dfs(int x) {
  14.     if (!x) return;
  15.     dfs(p[x]);
  16.     printf("%d ", a[x]);
  17. }
  18.  
  19. int main() {
  20.     set<int, comp> s;
  21.     s.insert(0);
  22.     a[0] = -2;
  23.    
  24.     int n; scanf("%d", &n);
  25.     for (int i = 1; i <= n; i++) {
  26.         scanf("%d", a+i);
  27.         bool done = false;
  28.         for (set<int, comp>::iterator it = s.begin(); it != s.end(); it++) {
  29.             int j = *it;
  30.             if (abs(a[j]-a[i]) == 1) continue;
  31.             s.erase(i);
  32.             len[i] = len[j] + 1;
  33.             s.insert(i);
  34.            
  35.             p[i] = j;
  36.             if (last[a[i]]) s.erase(last[a[i]]);
  37.             last[a[i]] = i;
  38.             done = true;
  39.             break;
  40.         }
  41.     }
  42.    
  43.     int x = *s.begin();
  44.     printf("%d\n", n-len[x]);
  45.     dfs(x);
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement