# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
528992 | SansPapyrus683 | Longest beautiful sequence (IZhO17_subsequence) | C++17 | 1 ms | 204 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <bit>
using std::cout;
using std::endl;
using std::vector;
using std::pair;
constexpr int MAX_BITS = 8;
constexpr int HALF_MAX = MAX_BITS / 2;
vector<vector<int>> prev_unique(const vector<int>& arr) {
vector<vector<int>> ret(arr.size());
for (int i = 0; i < arr.size(); i++) {
for (int j = i + 1; j < arr.size(); j++) {
ret[j].push_back(i);
if (arr[j] == arr[i]) {
break;
}
}
}
return ret;
}
/**
* https://oj.uz/problem/view/IZhO17_subsequence
* 5
* 5 3 5 3 5
* 10 1 20 1 20 should output
* 2
* 1 2
*/
int main() {
assert(MAX_BITS % 2 == 0);
// precalc
vector<vector<vector<int>>> and_counts(
1 << HALF_MAX, vector<vector<int>>(HALF_MAX + 1)
);
for (int i = 0; i < (1 << HALF_MAX); i++) {
for (int oi = 0; oi < (1 << HALF_MAX); oi++) {
and_counts[i][std::__popcount(i & oi)].push_back(oi);
}
}
int size;
std::cin >> size;
vector<int> arr(size);
for (int& i : arr) {
std::cin >> i;
}
vector<int> targets(size);
for (int& t : targets) {
std::cin >> t;
}
if (size <= 5000) {
vector<int> longest(size, 1);
vector<int> prev(size);
for (int i = 1; i < size; i++) {
prev[i] = i;
for (int p = 0; p < i; p++) {
if (std::__popcount(arr[i] & arr[p]) == targets[i]) {
longest[i] = std::max(longest[i], longest[p] + 1);
prev[i] = p;
}
}
}
int max = *std::max_element(longest.begin(), longest.end());
int i = 0;
for (; longest[i] != max; i++);
vector<int> seq{i};
while (prev[seq.back()] != seq.back()) {
seq.push_back(prev[seq.back()]);
}
cout << seq.size() << endl;
for (int i = seq.size() - 1; i > 0; i--) {
cout << seq[i] + 1 << ' ';
}
cout << seq.front() + 1 << endl;
} else {
vector<vector<int>> to_consider = prev_unique(arr);
vector<int> longest(size, 1);
vector<int> prev(size);
for (int i = 1; i < size; i++) {
prev[i] = i;
for (int p : to_consider[i]) {
if (std::__popcount(arr[i] & arr[p]) == targets[i]) {
longest[i] = std::max(longest[i], longest[p] + 1);
prev[i] = p;
}
}
}
int max = *std::max_element(longest.begin(), longest.end());
int i = 0;
for (; longest[i] != max; i++);
vector<int> seq{i};
while (prev[seq.back()] != seq.back()) {
seq.push_back(prev[seq.back()]);
}
cout << seq.size() << endl;
for (int i = seq.size() - 1; i > 0; i--) {
cout << seq[i] + 1 << ' ';
}
cout << seq.front() + 1 << endl;
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |