ams-2.cc

/*
 * Description:
 * An alternating monotonic sequence (AMS) is a monotonically increasing sequence which alternates between even and odd numbers. For example, {7,12,13,22} is an AMS, but {7,12,14,21} is not (though it is a monotonic sequence). Describe a dynamic program for finding a longest alternating monotonic subsequence of a given sequence.
 *
 * Input:
 * There are several test cases! In each test case, the first line contains an integer N (0 <= N <= 10000000). N is the length of the sequence. The following lines contain N integers that represent the sequence.
 *
 * Output:
 * For each test case, output in two lines. Between each test case, you should ouput one blank line. The first line contains an integer M, which is the length of alternating monotonic sequence. The second lines contains M integers represent the AMS of the sequence.
 *
 * Sample Input:
 * 7
 * 1 2 3 4 6 7 5
 *
 * 13
 * 3 5 6 2 5 4 19 5 6 9 12 8 11
 *
 * Sample Output:
 * 5
 * 1 2 3 6 7
 *
 * 6
 * 3 4 5 6 9 12
 */

#include <algorithm>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::stringstream;
using std::string;
using std::upper_bound;
using std::vector;

// Time(n) = O(nlog(n))
// Space(n) = O(n^2)

vector<int> AMS(const vector<int> &nums) {
  vector<int> dummy{numeric_limits<int>::max()};
  // odd_list[i]: smallest-odd-last-element lis whose length >= i + 1
  vector<vector<int>> odd_list{dummy};
  // even_list[i]: smallest-even-last-element lis whose length >= i + 1
  vector<vector<int>> even_list{dummy};
  auto cmp_s = [](const vector<int> &b, const vector<int> &k) { return b.back() < k.back(); };
  auto cmp_g = [](const int &k, const vector<int> &b) { return k < b.back(); };
  auto cmp_ge = [](const int &k, const vector<int> &b) { return k <= b.back(); };

  for (size_t i = 0; i < nums.size(); i++) {
    auto &key = nums.at(i);
    vector<vector<int>> *target = nullptr;
    vector<vector<int>> *another = nullptr;

    if (key % 2) {
      target = &odd_list;
      another = &even_list;
    } else {
      target = &even_list;
      another = &odd_list;
    }

    // find first element greater than key
    auto res = upper_bound(target->begin(), target->end(), key, cmp_g);
    if (res != target->end() && (res->size() == 1 || key > res->at(res->size() - 2))) {
      res->back() = key; // replace last one
    }
    // find last element smaller than key
    auto prefix = upper_bound(another->begin(), another->end(), key, cmp_ge);
    if (prefix == another->begin()) { continue; }

    auto beg_prefix = equal_range(another->begin(), prefix, *(prefix - 1), cmp_s);
    auto update = [&target, &key, &cmp_g](vector<vector<int>>::iterator &prefix_) {
      vector<int> appended(*prefix_);
      appended.push_back(key);
      auto res = upper_bound(target->begin(), target->end(), key, cmp_g);
      if (res != target->end()) {
        if (res->size() == appended.size()) {
          *res = appended; // replace
        }
      } else if (appended.size() > target->back().size()) {
        target->push_back(appended); // append
      }
    };

    for (auto iter = beg_prefix.first; iter != prefix; ++iter) {
      update(iter);
    }
  }

  // remove dummy
  if (odd_list.front() == dummy) { odd_list.erase(odd_list.begin()); }
  if (even_list.front() == dummy) { even_list.erase(even_list.begin()); }

  return odd_list.back().size() > even_list.back().size() ? odd_list.back() : even_list.back();
}

string SeqToString(const vector<int> &seq) {
  stringstream ss;
  ss << seq.size();
  if (seq.size()) { ss << endl; }
  for (size_t i = 0; i < seq.size(); i++) {
    ss << seq.at(i);
    if (i != seq.size() - 1) { ss << " "; }
  }
  return ss.str();
}

int main(void) {
  int n = 0;
  int a = 0;
  bool first = true;
  vector<int> nums;

  while (cin >> n) {
    nums.clear();
    while (n--) {
      cin >> a;
      nums.push_back(a);
    }
    if (!first) {
      cout << endl;
    } else {
      first = false;
    }
    cout << SeqToString(AMS(nums)) << endl;
  }

  return 0;
}