Submission #1333266

#TimeUsernameProblemLanguageResultExecution timeMemory
1333266fatelessLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
1 ms344 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;
template <class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}

const int inf = 1e18, N = 1e5 + 1, M = (1 << 8);
static int a[N], b[N], dp[N][M], p[N][M];
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];
    for (int i = 0; i <= n; i++) fill(dp[i], dp[i] + M, -inf);

    int ans = 0, st = 0;
    for (int i = 1; i <= n; i++) {
        for (int x = 0; x < M; x++) {
            if (chmax(dp[i][x], dp[i - 1][x])) p[i][x] = x;
            if (bitcount(x & a[i]) == b[i] && chmax(dp[i][a[i]], dp[i - 1][x] + 1)) p[i][a[i]] = x;
        }
        if (chmax(dp[i][a[i]], 1ll)) p[i][a[i]] = a[i];
    }
    for (int x = 0; x < M; x++) if (chmax(ans, dp[n][x])) st = x;
    cout << ans << '\n';
    vc<int> ord;

    int x = st;
    for (int i = n; i >= 1; i--) {
        int y = p[i][x];
        if (x != y) ord.pb(x);

        x = y;
    } ord.pb(x);
    reverse(all(ord)); int j = 1;
    for (int i = 0; i < ans; i++) {
        while (a[j] != ord[i]) j++;
        cout << 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...