test/yukicoder/1804.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 14:04:05+09:00
• Problem: https://yukicoder.me/problems/no/1804

Depends on

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

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1804
// 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(false);
 int N;
 cin >> N;
 vector<int> P(N);
 for (int i= 0; i < N; ++i) cin >> P[i];
 auto [_, cand]= longest_increasing_subsequence(P);
 vector<int> ans;
 for (auto &c: cand)
  if (c.size() == 1) ans.push_back(P[c[0]]);
 int m= ans.size();
 cout << m << '\n';
 for (int i= 0; i < m; ++i) cout << ans[i] << " \n"[i + 1 == m];
 if (!m) cout << " \n";
 return 0;
}

#line 1 "test/yukicoder/1804.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1804
// 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 7 "test/yukicoder/1804.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 vector<int> P(N);
 for (int i= 0; i < N; ++i) cin >> P[i];
 auto [_, cand]= longest_increasing_subsequence(P);
 vector<int> ans;
 for (auto &c: cand)
  if (c.size() == 1) ans.push_back(P[c[0]]);
 int m= ans.size();
 cout << m << '\n';
 for (int i= 0; i < m; ++i) cout << ans[i] << " \n"[i + 1 == m];
 if (!m) cout << " \n";
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	01_sample_1.txt	AC	7 ms	4 MB
g++-13	01_sample_2.txt	AC	6 ms	4 MB
g++-13	01_sample_3.txt	AC	6 ms	4 MB
g++-13	02_max_1.txt	AC	36 ms	8 MB
g++-13	02_max_10.txt	AC	38 ms	8 MB
g++-13	02_max_11.txt	AC	39 ms	8 MB
g++-13	02_max_12.txt	AC	38 ms	8 MB
g++-13	02_max_13.txt	AC	37 ms	8 MB
g++-13	02_max_14.txt	AC	37 ms	8 MB
g++-13	02_max_15.txt	AC	37 ms	8 MB
g++-13	02_max_2.txt	AC	37 ms	8 MB
g++-13	02_max_3.txt	AC	37 ms	8 MB
g++-13	02_max_4.txt	AC	37 ms	8 MB
g++-13	02_max_5.txt	AC	37 ms	8 MB
g++-13	02_max_6.txt	AC	37 ms	8 MB
g++-13	02_max_7.txt	AC	38 ms	8 MB
g++-13	02_max_8.txt	AC	38 ms	8 MB
g++-13	02_max_9.txt	AC	38 ms	8 MB
g++-13	03_medium_1.txt	AC	7 ms	4 MB
g++-13	03_medium_10.txt	AC	6 ms	4 MB
g++-13	03_medium_2.txt	AC	6 ms	4 MB
g++-13	03_medium_3.txt	AC	6 ms	4 MB
g++-13	03_medium_4.txt	AC	6 ms	4 MB
g++-13	03_medium_5.txt	AC	6 ms	4 MB
g++-13	03_medium_6.txt	AC	6 ms	4 MB
g++-13	03_medium_7.txt	AC	6 ms	4 MB
g++-13	03_medium_8.txt	AC	6 ms	4 MB
g++-13	03_medium_9.txt	AC	6 ms	4 MB
g++-13	04_min_1.txt	AC	6 ms	4 MB
g++-13	04_min_2.txt	AC	5 ms	4 MB
g++-13	04_min_3.txt	AC	5 ms	4 MB
g++-13	04_min_4.txt	AC	5 ms	4 MB
g++-13	04_min_5.txt	AC	5 ms	4 MB
g++-13	04_min_6.txt	AC	5 ms	4 MB
g++-13	04_min_7.txt	AC	5 ms	4 MB
g++-13	05_hand_1.txt	AC	68 ms	41 MB
g++-13	05_hand_2.txt	AC	71 ms	41 MB
g++-13	05_hand_3.txt	AC	25 ms	10 MB
g++-13	05_hand_4.txt	AC	25 ms	10 MB
g++-13	05_hand_5.txt	AC	6 ms	4 MB
clang++-18	01_sample_1.txt	AC	6 ms	4 MB
clang++-18	01_sample_2.txt	AC	6 ms	4 MB
clang++-18	01_sample_3.txt	AC	6 ms	4 MB
clang++-18	02_max_1.txt	AC	37 ms	8 MB
clang++-18	02_max_10.txt	AC	37 ms	8 MB
clang++-18	02_max_11.txt	AC	37 ms	8 MB
clang++-18	02_max_12.txt	AC	37 ms	8 MB
clang++-18	02_max_13.txt	AC	37 ms	8 MB
clang++-18	02_max_14.txt	AC	36 ms	8 MB
clang++-18	02_max_15.txt	AC	37 ms	8 MB
clang++-18	02_max_2.txt	AC	37 ms	8 MB
clang++-18	02_max_3.txt	AC	37 ms	8 MB
clang++-18	02_max_4.txt	AC	37 ms	8 MB
clang++-18	02_max_5.txt	AC	36 ms	8 MB
clang++-18	02_max_6.txt	AC	36 ms	8 MB
clang++-18	02_max_7.txt	AC	36 ms	8 MB
clang++-18	02_max_8.txt	AC	37 ms	8 MB
clang++-18	02_max_9.txt	AC	37 ms	8 MB
clang++-18	03_medium_1.txt	AC	6 ms	4 MB
clang++-18	03_medium_10.txt	AC	6 ms	4 MB
clang++-18	03_medium_2.txt	AC	6 ms	4 MB
clang++-18	03_medium_3.txt	AC	6 ms	4 MB
clang++-18	03_medium_4.txt	AC	6 ms	4 MB
clang++-18	03_medium_5.txt	AC	6 ms	4 MB
clang++-18	03_medium_6.txt	AC	6 ms	4 MB
clang++-18	03_medium_7.txt	AC	6 ms	4 MB
clang++-18	03_medium_8.txt	AC	6 ms	4 MB
clang++-18	03_medium_9.txt	AC	6 ms	4 MB
clang++-18	04_min_1.txt	AC	5 ms	4 MB
clang++-18	04_min_2.txt	AC	6 ms	4 MB
clang++-18	04_min_3.txt	AC	5 ms	4 MB
clang++-18	04_min_4.txt	AC	6 ms	4 MB
clang++-18	04_min_5.txt	AC	6 ms	4 MB
clang++-18	04_min_6.txt	AC	5 ms	4 MB
clang++-18	04_min_7.txt	AC	5 ms	4 MB
clang++-18	05_hand_1.txt	AC	71 ms	41 MB
clang++-18	05_hand_2.txt	AC	73 ms	41 MB
clang++-18	05_hand_3.txt	AC	26 ms	10 MB
clang++-18	05_hand_4.txt	AC	25 ms	10 MB
clang++-18	05_hand_5.txt	AC	6 ms	4 MB

Back to top page