Submission #528993

#	Time	Username	Problem	Language	Result	Execution time	Memory
528993		SansPapyrus683	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	370 ms	106780 KiB

subsequence

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

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

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() {
    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 {
        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]) {
                    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;
    }
}

Compilation message (stderr)

subsequence.cpp: In function 'std::vector<std::vector<int> > prev_unique(const std::vector<int>&)':
subsequence.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < arr.size(); i++) {
      |                     ~~^~~~~~~~~~~~
subsequence.cpp:13:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for (int j = i + 1; j < arr.size(); j++) {
      |                             ~~^~~~~~~~~~~~

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