Submission #1198562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198562		SnowRaven52	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2181 ms	95976 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

const int B = 10;
const int M = 1 << B;

struct state {
    int length = 0;
    int last_idx = -1;
};

int main(){
    int bc[M][M];
    for(int i = 0; i < M; ++i)
        for(int j = 0; j < M; ++j)
            bc[i][j] = __builtin_popcount(i & j);

    int n; cin >> n;
    vector<int> a(n), k(n);
    for(int &x : a) cin >> x;
    for(int &x : k) cin >> x;

    state dp[M][M][B+1];
    int best_len = 1, best_end = 0;
    vector<int> prev_idx(n);
    iota(prev_idx.begin(), prev_idx.end(), 0);

    for(int i = 0; i < n; ++i) {
        int hi = a[i] >> B, lo = a[i] & (M - 1), cur_len = 1, cur_prev = i;
        for(int prev_hi = 0; prev_hi < M; ++prev_hi) {
            int needed = k[i] - bc[prev_hi][hi];
            if(needed < 0 || needed > B)
                continue;
            auto &st = dp[prev_hi][lo][needed];
            if(st.length + 1 > cur_len) {
                cur_len = st.length + 1;
                cur_prev = st.last_idx;
            }
        }
        prev_idx[i] = cur_prev;
        if(cur_len > best_len) {
            best_len = cur_len;
            best_end = i;
        }
        for(int next_lo = 0; next_lo < M; ++next_lo) {
            int c = bc[lo][next_lo];
            auto &st = dp[hi][next_lo][c];
            if(cur_len > st.length) {
                st.length   = cur_len;
                st.last_idx = i;
            }
        }
    }
    vector<int> sequence;
    for(int x = best_end; prev_idx[x] != x; x = prev_idx[x])
        sequence.push_back(x);
    sequence.push_back(sequence.empty() ? best_end : prev_idx[sequence.back()]);
    reverse(sequence.begin(), sequence.end());
    cout << best_len << endl;
    for(int idx : sequence)
        cout << idx + 1 << " ";
    cout << endl;
}

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