Submission #528991

#	Time	Username	Problem	Language	Result	Execution time	Memory
528991		SansPapyrus683	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	296 KiB

subsequence

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

Compilation message (stderr)

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

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