Submission #1350597

#TimeUsernameProblemLanguageResultExecution timeMemory
1350597Rafael_AugustoLongest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
3928 ms223612 KiB
#include <bits/stdc++.h>
using namespace std;

// Muito cuidado por aqui ↓
//#define int long long
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)

typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXM = (1<<10);
const int lg =20;
const int mlg=10;

int dp[MAXM][MAXM][lg+7];
int fa[MAXM][MAXM][lg+7];
//fixo[updt][qury]

int cnt(int x, int y){ return __builtin_popcount(x&y); }

bool ckmax(int& x, int y){
    if(x < y){ x=y; return 1; }
    return 0;
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;

    int a[n+1], k[n+1];

    fall(i, 1, n+1) cin >> a[i];

    fall(i, 1, n+1) cin >> k[i];

    int ans[n+1]; ans[0]=0;
    int pai[n+1]; pai[0]=0;

    fall(i, 1, n+1){
        int l=0, r=0;

        ans[i]=1, pai[i]=0;

        fall(j, 0, mlg) r += (1<<j)&a[i];
        fall(j, mlg, lg) if((1<<j)&a[i]) l += (1<<(j-mlg));

        fall(j, 0, MAXM){
            int q = k[i]-cnt(j, l);
            if(q >= 0){
                if(ckmax(ans[i], dp[j][r][q]+1)) pai[i]=fa[j][r][q];
            }
        }

        fall(j, 0, MAXM){
            if(ckmax(dp[l][j][cnt(r, j)], ans[i])) fa[l][j][cnt(r, j)]=i;
        }
    }

    int mx=0, id=-1;

    fall(i, 0, n+1) if(ckmax(mx, ans[i])) id=i;

    cout << mx << "\n";

    vector<int> v;

    while(id) v.pb(id), id = pai[id];

    reverse(all(v));

    fall(i, 0, (int)v.size()) cout << v[i] << " \n"[i+1 == (int)v.size()];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...