Submission #1333263

#TimeUsernameProblemLanguageResultExecution timeMemory
1333263fatelessLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
375 ms327680 KiB
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define now chrono::steady_clock::now().time_since_epoch().count()
#define speedup cin.tie(0)->sync_with_stdio(0)
#define bitcount __builtin_popcount
#define all(x) begin(x), end(x)
#define int long long
#define pb push_back
#define arr array
#define vc vector

using ll = long long;
const int inf = 1e18, N = 1e5 + 1, M = (1 << 8);
static int a[N], b[N], dp[M], p[M];
template <class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}

inline void solve () {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    fill(dp, dp + M, -inf);

    int ans = 0, st = 0;
    for (int i = 1; i <= n; i++) {
        for (int x = 0; x < M; x++) {
            int mask = (x & a[i]);
            if (bitcount(mask) == b[i])
                if (chmax(dp[a[i]], dp[x] + 1))
                    p[a[i]] = x;
        }

        chmax(dp[a[i]], 1ll);
        if (chmax(ans, dp[a[i]])) st = a[i];
    }

    vc<int> ord;
    cout << ans << '\n';
    while (st) {
        ord.pb(st);
        st = p[st];
    }
    int j = 1;
    reverse(all(ord));
    for (int i = 0; i < ord.size(); i++) {
        while (a[j] != ord[i]) j++;
        cout << j << ' ';
        j++;
    }
}

signed main() {
    speedup;
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...