結果
問題 | No.1804 Intersection of LIS |
ユーザー |
![]() |
提出日時 | 2022-01-07 22:18:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 2,776 bytes |
コンパイル時間 | 2,187 ms |
コンパイル使用メモリ | 203,048 KB |
最終ジャッジ日時 | 2025-01-27 09:34:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 1000000007; // constexpr int MOD = 998244353; constexpr int DY[]{1, 0, -1, 0}, DX[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}, DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; template <typename T> std::vector<T> longest_increasing_subsequence(const std::vector<T> &a, bool is_strict = true) { const T inf = std::numeric_limits<T>::max(); const int n = a.size(); std::vector<int> idx(n); std::vector<T> tmp(n, inf); for (int i = 0; i < n; ++i) { if (is_strict) { idx[i] = std::distance(tmp.begin(), std::lower_bound(tmp.begin(), tmp.end(), a[i])); } else { idx[i] = std::distance(tmp.begin(), std::upper_bound(tmp.begin(), tmp.end(), a[i])); } tmp[idx[i]] = a[i]; } int res_size = std::distance(tmp.begin(), std::lower_bound(tmp.begin(), tmp.end(), inf)); std::vector<T> res(res_size--); for (int i = n - 1; res_size >= 0 && i >= 0; --i) { if (idx[i] == res_size) { res[res_size--] = a[i]; } } return res; } int main() { int n; cin >> n; vector<int> p(n); REP(i, n) cin >> p[i], --p[i]; vector<int> okayu(n, INF), idx(n); REP(i, n) { idx[i] = upper_bound(ALL(okayu), p[i]) - okayu.begin(); okayu[idx[i]] = p[i]; } const int lis = lower_bound(ALL(okayu), INF) - okayu.begin(); vector<int> mx(lis, -INF); vector<vector<int>> pos(lis); for (int i = n - 1; i >= 0; --i) { if (idx[i] + 1 == lis || p[i] < mx[idx[i] + 1]) { pos[idx[i]].emplace_back(i); chmax(mx[idx[i]], p[i]); } } vector<int> ans; REP(i, lis) { if (pos[i].size() == 1) ans.emplace_back(pos[i].front()); } sort(ALL(ans)); // { // const int lis = longest_increasing_subsequence(p).size(); // vector<int> ans2; // REP(i, n) { // vector<int> a = p; // a.erase(a.begin() + i); // if (longest_increasing_subsequence(a).size() < lis) ans2.emplace_back(i); // } // assert(ans == ans2); // } const int m = ans.size(); cout << m << '\n'; REP(i, m) { cout << p[ans[i]] + 1; if (i + 1 < m) cout << ' '; } cout << '\n'; return 0; }