Submission #507029

#TimeUsernameProblemLanguageResultExecution timeMemory
507029dannyboy20031204Longest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
108 ms2892 KiB
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
void db() {cout << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {cout << a << ' ', db(b...);}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
#define pii pair<int, int>
const int inf = 1e9, N = 120, _N = 501, mod = 998244353;
pair<int, int> p[_N][N]{};
pii get(pii u){
    return p[u.fi][u.se] = p[u.fi][u.se] == u ? u : get(p[u.fi][u.se]);
}
void merge(pii a, pii b){
    b = get(b);
    p[a.fi][a.se] = b;
}
int main(){
    
    file;
    /*
    int n;
    cin >> n;
    int a[n], tot = 0;
    for (int &i : a) cin >> i, tot += i;
    if (tot % 2) return cout << 0 << '\n', 0;
    int cnt[N]{};
    bool dp[N]{}, can[_N][N]{};
    for (int i = 0; i < N; i++) p[n][i] = {n, i};
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j < N; j++) p[i][j] = p[i + 1][j];
        for (int j = a[i]; j < N; j++) merge(p[i][j], p[i + 1][j - a[i]]);
    }
    dp[0] = 1;
    //db(p[3][8]);
    for (int i = 0; i < n; i++){
        bool can[N]{};
        for (int j = 0; j < N; j++) if (dp[j]) {
            auto u = get(i + 1, j);
            can[u.fi][u.se] = 1;
        }
        for (int j = 0; j < N; j++) {
            auto u = get(i + 1, j);
            if (can[u.fi][u.se] and j * 2 >= tot - a[i]){
                db(i, j, j * 2 - tot + a[i]);
                cnt[j * 2 - tot + a[i]]++;
            }
        }
        for (int j = N - 1; j >= a[i]; j--) dp[j] |= dp[j - a[i]];
    }
    if (!dp[tot / 2]) return cout << 0 << '\n', 0;
    vector<int> ans;
    for (int i = 1; i < N; i++) if (cnt[i] == n) ans.push_back(i);
    cout << ans.size() << '\n';
    for (int i : ans) cout << i << ' ';
    */
    int n;
    cin >> n;
    if (n <= 5000){
        int a[n], k[n], dp[n]{}, par[n], ans = 0, tar = 0;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> k[i];
        for (int i = 0; i < n; i++){
            dp[i] = 1;
            par[i] = -1;
            for (int j = 0; j < i; j++){
                if (__builtin_popcount(a[i] & a[j]) == k[i]){
                    if (dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        par[i] = j;
                    }
                }
            }
            if (dp[i] > ans) ans = dp[i], tar = i;
        }
        vector<int> v;
        for (int i = tar; i >= 0; i = par[i]) v.push_back(i);
        reverse(v.begin(), v.end());
        cout << v.size() << '\n';
        for (int i : v) cout << i + 1 << ' ';
        return 0;
    }
    int a[n], k[n], dp[(1 << 8)]{}, par[n], ma[(1 << 8)], ans = 0, tar = 0;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> k[i];
    for (int i = 0; i < n; i++){
        int tmp = 1;
        par[i] = -1;
        if (i) for (int j = 0; j < (1 << 8); j++) if (__builtin_popcount(a[i] & j) == k[i]){
            if (tmp < dp[j] + 1) tmp = dp[j] + 1, par[i] = ma[j];
        }
        if (tmp > dp[a[i]]) dp[a[i]] = tmp, ma[a[i]] = i; 
        if (tmp > ans) ans = tmp, tar = i;
    }
    cout << ans <<'\n';
    vector<int> v;
    for (int i = tar; i >= 0; i = par[i]) v.push_back(i);
    reverse(v.begin(), v.end());
    for (int i : v) cout << i + 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...