Submission #1142735

#TimeUsernameProblemLanguageResultExecution timeMemory
1142735kitlixLongest beautiful sequence (IZhO17_subsequence)C++20
40 / 100
6092 ms3400 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& el : a)
        cin >> el;
    vector<int> k(n);
    for (auto& el : k)
        cin >> el;
    int mxalalal = *max_element(a.begin(), a.end());
    if (mxalalal < (1 << 8)) {
        int MAXA = (1 << 8);
        vector<pair<int, int>> dp(MAXA);
        vector<int> par(n);
        for (int i = 0; i < n; ++i) {
            int bst = 1, bstpa = -1;
            for (int j = 0; j < MAXA; ++j) {
                if (__builtin_popcount(a[i] & j) == k[i]) {
                    if (dp[j].first + 1 > bst) {
                        bst = dp[j].first + 1;
                        bstpa = dp[j].second;
                    }
                }
            }
            par[i] = bstpa;
            dp[a[i]] = max(dp[a[i]], pair<int, int>{bst, i});
        }
        int mx = 0, mxi = 0;
        for (int i = 0; i < MAXA; ++i) {
            if (dp[i].first > mx) {
                mx = dp[i].first;
                mxi = dp[i].second;
            }
        }
        cout << mx << '\n';
        int cur = mxi;
        vector<int> ans;
        while (cur != -1) {
            ans.push_back(cur);
            cur = par[cur];
        }
        reverse(ans.begin(), ans.end());
        for (auto el : ans)
            cout << el + 1 << ' ';
    } else {
        vector<int> dp(n);
        vector<int> par(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            par[i] = -1;
            for (int j = 0; j < i; ++j) {
                if (__builtin_popcount(a[i] & a[j]) == k[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        par[i] = j;
                    }
                }
            }
        }
        int mx = 0, mxi = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[i] > mx) {
                mx = dp[i];
                mxi = i;
            }
        }
        cout << mx << '\n';
        int cur = mxi;
        vector<int> ans;
        while (cur != -1) {
            ans.push_back(cur);
            cur = par[cur];
        }
        reverse(ans.begin(), ans.end());
        for (auto el : ans)
            cout << el + 1 << ' ';
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...