Submission #1294493

#TimeUsernameProblemLanguageResultExecution timeMemory
1294493LIALongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
1 ms336 KiB
//
// Created by liasa on 23/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (int i = s; i < e; ++i)

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    v<int> a(n), k(n);
    lp(i, 0, n) cin >> a[i];
    lp(i, 0, n) cin >> k[i];

    int ans = 0, idx = 0;
    ll mx = (1LL << 8);
    v<int> dp(mx, 1), pr(mx, -1);
    set<ll> in;
    lp(i, 1, n + 1) {
        dp[i] = 1;
        ll val = a[i - 1];
        for (auto it: in) {
            ll cnt = __builtin_popcount(it & a[i - 1]);
            if (cnt == k[i - 1] && dp[val] < dp[it] + 1) {
                dp[val] = dp[it] + 1;
                pr[val] = it;
            }
        }
        in.insert(a[i - 1]);
        if (ans<dp[val]) {
            ans = dp[val];
            idx = i;
        }
    }

    v<int> vec;

    while (idx != -1) {
        vec.push_back(idx);
        idx = pr[idx];
    }
    cout << ans << '\n';
    reverse(vec.begin(), vec.end());
    vector<ll> ansi;
    ll j =0 ;
    lp(i,0,n) {
        if (j==vec.size()) break;
        if (a[i] == vec[j]) {
            j++;
            ansi.push_back(i);
        }
    }
    for (auto it : ansi) cout<<it+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...