제출 #1333283

#제출 시각아이디문제언어결과실행 시간메모리
1333283fatelessLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
0 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 << 9);
static int a[N], b[N], dp[M], p[N], mp[M];
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];
    memset(dp, -1, sizeof(dp)); memset(mp, 0, sizeof(mp));

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