Submission #1333287

#TimeUsernameProblemLanguageResultExecution timeMemory
1333287fatelessLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
596 ms15652 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;}
static int bits[1 << 10][1 << 10];

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

    int M = *max_element(all(a)) + 1;
    vc<int> dp (M, -1), mp (M, 0);

    for (int i = 0; i < M; i++)
        for (int j = 0; j < M; j++)
            bits[i][j] = bitcount(i & j);

    int ans = 0, st = 0;
    for (int i = 1; i <= n; i++) {
        int cur = 1; p[i] = 0;
        for (int v = 0; v < M; v++)
            if (bits[v][a[i]] == b[i])
                if (chmax(cur, dp[v] + 1)) p[i] = mp[v];

        if (chmax(dp[a[i]], cur)) mp[a[i]] = i;
        if (chmax(ans, cur)) st = i;
    }
    cout << ans << "\n";
    
    vc<int> ord;
    while (st) {
        ord.pb(st);
        st = p[st];
    } 
    
    reverse(all(ord));
    for (int x : ord) cout << x << ' ';
}

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...