Submission #1368955

#TimeUsernameProblemLanguageResultExecution timeMemory
1368955mhn_neekLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
2 ms4420 KiB
//In the name of God
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
const lli N=1e5+100;
#define all(v) v.begin(),v.end()
#define migmig ios_base::sync_with_stdio(false),cout.tie(0), cin.tie(0);
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define FOR(x,n) for(lli x = 0; x < n; x++)
#define FORS(x,n) for(lli x = 1; x <= n; x++)
#define endl "\n"
#define sep " "
#define SZ(X) (lli)X.size()
#define debug(x) cerr << (#x) << " " << (x) << endl

lli tmp;
lli n,A[N],k[N];
lli cnt[(1 << 21)];
pii dp[N];
pii f[(1 << 21)];
int main(){
    migmig;
    FOR(i,(1 << 20)){
        cnt[i] = __builtin_popcount(i);
    }
    cin>>n;
    FORS(i,n){
        cin>>A[i];
    }
    FORS(i,n){
        cin>>k[i];
    }

    vector<lli> t;
    FORS(i,n){
        FOR(j,1024){
            if(cnt[A[i]&j] == k[i]){
                dp[i] = max(dp[i],MP(f[j].fi+1,f[j].se));
            }
        }
        pii p;
        for(auto j : t){
            if(cnt[A[i]&A[j]] == k[i]){
                dp[i] = max(dp[i],MP(dp[j].fi+1,j));
            }
        }

        f[A[i]] = max(f[A[i]],MP(dp[i].fi,i));
        if(A[i ] >= 1024)t.PB(i);
    }

    lli ans = 0;
    lli las = 0;
    FORS(i,n){
        ans = max(ans,dp[i].fi);
        if(ans == dp[i].fi)las = i;
    }

    ve v;
    while(las > 0){
        v.PB(las);
        las = dp[las].se;
    
    }

    cout<<SZ(v)<<endl;
    reverse(all(v));
    for(auto i : v)cout<<i<<" ";

}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...