Submission #532344

#	Time	Username	Problem	Language	Result	Execution time	Memory
532344		SansPapyrus683	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6005 ms	4148 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;
    }
  
    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