This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence" #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #include "../lis.hpp" void solve([[maybe_unused]] int ith) { int n; cin >> n; vector<int> a(n); for (auto &x : a) cin >> x; auto ans = lis(a); cout << ans.size() << '\n'; for (auto idx : ans) cout << idx << ' '; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc = 1; // cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); }
#line 1 "dp/test/Longest_Increasing_Subsequence.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence" #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #line 1 "dp/lis.hpp" // return a vector contains indices of the LIS template <typename T> vector<int> lis(const vector<T>& a) { int n = (int)a.size(); vector<int> b(n + 1, 0), f(n, 0); int ans = 0; for (int i = 0; i < n; i++) { f[i] = lower_bound(begin(b) + 1, begin(b) + ans + 1, a[i]) - begin(b); ans = max(ans, f[i]); b[f[i]] = a[i]; } int req = ans; vector<int> res; for (int i = n - 1; i >= 0; i--) { if (f[i] == req) { res.push_back(i); --req; } } reverse(begin(res), end(res)); return res; } #line 11 "dp/test/Longest_Increasing_Subsequence.test.cpp" void solve([[maybe_unused]] int ith) { int n; cin >> n; vector<int> a(n); for (auto &x : a) cin >> x; auto ans = lis(a); cout << ans.size() << '\n'; for (auto idx : ans) cout << idx << ' '; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); int tc = 1; // cin >> tc; for (int i = 1; i <= tc; ++i) solve(i); }