test/yosupo/longest_increasing_subsequence.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 14:04:05+09:00
• Problem: https://judge.yosupo.jp/problem/longest_increasing_subsequence

Depends on

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

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/longest_increasing_subsequence
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 128
#include <iostream>
#include <vector>
#include "src/Misc/longest_increasing_subsequence.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 vector<int> A(N);
 for (int i= 0; i < N; ++i) cin >> A[i];
 auto [_, cand]= longest_increasing_subsequence(A);
 int K= cand.size();
 cout << K << '\n';
 for (int i= 0; i < K; ++i) cout << cand[i].front() << " \n"[i + 1 == K];
 return 0;
}

#line 1 "test/yosupo/longest_increasing_subsequence.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/longest_increasing_subsequence
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 128
#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 7 "test/yosupo/longest_increasing_subsequence.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 vector<int> A(N);
 for (int i= 0; i < N; ++i) cin >> A[i];
 auto [_, cand]= longest_increasing_subsequence(A);
 int K= cand.size();
 cout << K << '\n';
 for (int i= 0; i < K; ++i) cout << cand[i].front() << " \n"[i + 1 == K];
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	example_01	AC	4 ms	4 MB
g++-13	hand_max_00	AC	105 ms	66 MB
g++-13	hand_min_00	AC	40 ms	15 MB
g++-13	max_random_00	AC	60 ms	11 MB
g++-13	max_random_01	AC	60 ms	11 MB
g++-13	max_random_02	AC	60 ms	11 MB
g++-13	max_random_03	AC	60 ms	11 MB
g++-13	max_random_04	AC	59 ms	11 MB
g++-13	random_00	AC	47 ms	9 MB
g++-13	random_01	AC	55 ms	11 MB
g++-13	random_02	AC	10 ms	4 MB
g++-13	random_03	AC	51 ms	10 MB
g++-13	random_04	AC	35 ms	8 MB
g++-13	small_00	AC	5 ms	4 MB
g++-13	small_01	AC	4 ms	4 MB
g++-13	small_02	AC	4 ms	4 MB
g++-13	small_03	AC	4 ms	4 MB
g++-13	small_04	AC	4 ms	4 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	example_01	AC	4 ms	4 MB
clang++-18	hand_max_00	AC	106 ms	66 MB
clang++-18	hand_min_00	AC	40 ms	15 MB
clang++-18	max_random_00	AC	60 ms	11 MB
clang++-18	max_random_01	AC	60 ms	11 MB
clang++-18	max_random_02	AC	60 ms	11 MB
clang++-18	max_random_03	AC	60 ms	11 MB
clang++-18	max_random_04	AC	59 ms	11 MB
clang++-18	random_00	AC	47 ms	9 MB
clang++-18	random_01	AC	56 ms	11 MB
clang++-18	random_02	AC	11 ms	4 MB
clang++-18	random_03	AC	52 ms	10 MB
clang++-18	random_04	AC	35 ms	8 MB
clang++-18	small_00	AC	5 ms	4 MB
clang++-18	small_01	AC	4 ms	4 MB
clang++-18	small_02	AC	4 ms	4 MB
clang++-18	small_03	AC	4 ms	4 MB
clang++-18	small_04	AC	4 ms	4 MB

Back to top page