test/atcoder/abc354_f.test.cpp

View this file on GitHub
Last update: 2025-08-08 18:52:16+09:00
Problem: https://atcoder.jp/contests/abc354/tasks/abc354_f

Depends on

最長増加部分列 (src/Misc/longest_increasing_subsequence.hpp)

Code

// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc354/tasks/abc354_f
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Misc/longest_increasing_subsequence.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int T;
 cin >> T;
 while (T--) {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i= 0; i < N; ++i) cin >> A[i];
  auto [idx, _]= longest_increasing_subsequence(A);
  vector<int> ans;
  for (int i= 0; i < N; ++i)
   if (idx[i] != -1) ans.push_back(i);
  int m= ans.size();
  cout << m << '\n';
  for (int i= 0; i < m; ++i) cout << ans[i] + 1 << " \n"[i + 1 == m];
 }
 return 0;
}

#line 1 "test/atcoder/abc354_f.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc354/tasks/abc354_f
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/Misc/longest_increasing_subsequence.hpp"
#include <algorithm>
template <class T> std::pair<std::vector<int>, std::vector<std::vector<int>>> longest_increasing_subsequence(const std::vector<T> &a, bool strict= true) {
 int n= a.size();
 std::vector<int> idx(n);
 std::vector<T> dp(n);
 int len= 0;
 if (strict)
  for (int i= 0; i < n; ++i) {
   auto it= std::lower_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 else
  for (int i= 0; i < n; ++i) {
   auto it= std::upper_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 std::vector<std::vector<int>> cand(len);
 for (int i= n; i--;) {
  if (idx[i] == len - 1 || (!cand[idx[i] + 1].empty() && a[i] < a[cand[idx[i] + 1].back()])) cand[idx[i]].emplace_back(i);
  else idx[i]= -1;
 }
 for (auto &c: cand) std::reverse(c.begin(), c.end());
 return {idx, cand};
}
#line 8 "test/atcoder/abc354_f.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int T;
 cin >> T;
 while (T--) {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i= 0; i < N; ++i) cin >> A[i];
  auto [idx, _]= longest_increasing_subsequence(A);
  vector<int> ans;
  for (int i= 0; i < N; ++i)
   if (idx[i] != -1) ans.push_back(i);
  int m= ans.size();
  cout << m << '\n';
  for (int i= 0; i < m; ++i) cout << ans[i] + 1 << " \n"[i + 1 == m];
 }
 return 0;
}