test/math/Longest_Increasing_Subsequence.test.cpp

View this file on GitHub
Last update: 2023-10-26 02:38:17+09:00
Problem: https://judge.yosupo.jp/problem/longest_increasing_subsequence

Depends on

LIS (math/longest_increasing_subsequence.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"

#include "../../math/longest_increasing_subsequence.hpp"

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &x : a) std::cin >> x;
    auto ans = ebi::LIS(a, true);
    int k = ans.size();
    std::cout << k << '\n';
    for (int i = 0; i < k; i++) {
        std::cout << ans[i] << " \n"[i == k - 1];
    }
}

#line 1 "test/math/Longest_Increasing_Subsequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"

#line 2 "math/longest_increasing_subsequence.hpp"

#include <algorithm>
#include <limits>
#include <vector>

namespace ebi {

template <class T> std::vector<T> LIS(const std::vector<T> &a, bool narrowly) {
    std::vector<T> ret = {std::numeric_limits<T>::max()};
    std::vector<int> used;
    used.reserve(a.size());
    for (auto x : a) {
        auto itr = narrowly ? std::lower_bound(ret.begin(), ret.end(), x)
                            : std::upper_bound(ret.begin(), ret.end(), x);
        used.emplace_back(itr - ret.begin());
        if (itr == ret.end())
            ret.emplace_back(x);
        else
            *itr = x;
    }
    int len = ret.size();
    int idx = len - 1;
    T now = std::numeric_limits<T>::max();
    std::vector<int> lis(len);
    for (int i = int(a.size()) - 1; i >= 0; i--) {
        if (used[i] == idx && a[i] + int(narrowly) <= now) {
            now = a[i];
            lis[idx--] = i;
        }
    }
    return lis;
}

}  // namespace ebi
#line 4 "test/math/Longest_Increasing_Subsequence.test.cpp"

#include <iostream>
#line 7 "test/math/Longest_Increasing_Subsequence.test.cpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &x : a) std::cin >> x;
    auto ans = ebi::LIS(a, true);
    int k = ans.size();
    std::cout << k << '\n';
    for (int i = 0; i < k; i++) {
        std::cout << ans[i] << " \n"[i == k - 1];
    }
}