Submission #1307130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307130		1an	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	1 ms	580 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

struct state {
    int len = -1, end = -1;
};

int main () {
    int n;
    cin >> n;

    vector<int> a(n), k(n), prev(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n; i++)
        cin >> k[i];

    for (int i = 0; i < n; i++)
        prev[i] = i;

    vector<vector<int>> bc(1 << 8, vector<int>(1 << 8));
    for (int i = 0; i < (1 << 8); i++)
        for (int j = 0; j < (1 << 8); j++)
            bc[i][j] = __builtin_popcount(i & j);

    vector<state> dp1(1 << 8), dp2(1 << 8);
    dp1[a[0]] = {1, 0};

    int best_m = 1, m_idx = 0;

    for (int i = 1; i < n; i++) {
        if (dp2[a[i]].len == -1)
            dp2[a[i]] = {1, i};

        for (int mask = 0; mask < (1 << 8); mask++) {
            if (1 + dp1[mask].len > dp2[a[i]].len && bc[mask][a[i]] == k[i]) {
                dp2[a[i]] = {1 + dp1[mask].len, i};
                prev[i] = dp1[mask].end;

                if (dp2[a[i]].len > best_m) {
                    best_m = dp2[a[i]].len;
                    m_idx = i;
                }
            }

            if (dp1[mask].len > dp2[mask].len) {
                dp2[mask] = {dp1[mask].len, dp1[mask].end};
            }
        }

        swap(dp1, dp2);
        fill(dp2.begin(), dp2.end(), state(-1, -1));
    }

    printf("%d\n", best_m);

    stack<int> st;
    while (true) {
        st.push(m_idx);

        if (prev[m_idx] == m_idx)
            break;

        m_idx = prev[m_idx];
    }

    while (!st.empty()) {
        printf("%d ", st.top() + 1);
        st.pop();
    }
}

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