fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. std::vector<int> A, lis, lis_pos, pos_prev;
  6. int last_pos;
  7. void print_prev(int pos) {
  8.     if (pos != pos_prev[pos])
  9.         print_prev(pos_prev[pos]);
  10.     printf("%d ", A[pos]);
  11. }
  12.  
  13. int main() {
  14.     int x;
  15.     for (int pos = 0; scanf("%d", &x) == 1; ++pos) {
  16.         A.push_back(x);
  17.         pos_prev.push_back(pos);
  18.         if (lis.size() == 0 or lis.back() < x) {
  19.             lis.push_back(x);
  20.             lis_pos.push_back(pos);
  21.             if (lis.size() > 1)
  22.                 pos_prev[pos] = lis_pos[lis.size()-2];
  23.             last_pos = pos;
  24.         } else {
  25.             auto it = std::lower_bound(lis.begin(), lis.end(), x);
  26.             size_t pos_replace = it - lis.begin();
  27.             lis[pos_replace] = x;
  28.             lis_pos[pos_replace] = pos;
  29.             if (pos_replace > 0)
  30.                 pos_prev[pos] = lis_pos[pos_replace-1];
  31.             if (pos_replace == lis.size()-1)
  32.                 last_pos = pos;
  33.         }
  34.     }
  35.  
  36.     print_prev(last_pos);
  37.     printf("\n");
  38.  
  39.     return 0;
  40. }
  41.  
Success #stdin #stdout 0s 3416KB
comments (?)
stdin
copy 
8 10 4 13 16 5 3 3 1 13 18 10 2 8 17
stdout
copy 
8 10 13 16 17
https://ideone.com/XYtuU7
language:
C++14 (gcc 8.3)
created:
9 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!