제출 #531146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531146		SansPapyrus683	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6057 ms	3964 KiB

subsequence

#include <iostream>
#include <vector>
#include <algorithm>
#include <bit>
#include <map>

using std::cout;
using std::endl;
using std::vector;
using std::pair;

/**
 * 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() {
    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]) {
                    if (longest[p] + 1 > longest[i]) {
                        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 {
        std::map<int, pair<int, int>> got_seqs{{arr[0], {1, 0}}};
        vector<int> prev(size);
        int longest = 1;
        int longest_end = 0;
        for (int i = 1; i < size; i++) {
            int n = arr[i];
            int this_max = 1;
            prev[i] = i;
            for (const auto& [p, p_info] : got_seqs) {
                if (std::__popcount(n & p) == targets[i]) {
                    if (p_info.first + 1 > this_max) {
                        this_max = p_info.first + 1;
                        prev[i] = p_info.second;
                    }
                }
            }
            if (this_max > got_seqs[n].first) {
                got_seqs[n] = {this_max, i};
            }
            if (this_max > longest) {
                longest = this_max;
                longest_end = i;
            }
        }

        vector<int> seq{longest_end};
        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;
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 60