#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int sqr=320;
int A[MAXN],B[MAXN],dp[MAXN],trace[MAXN];
pair<int,int> F[1024][1024][21];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>A[i];
for(int i=1;i<=n;i++) cin>>B[i];
int pre=1;
for(int i=0;i<1024;i++) for(int j=0;j<1024;j++) for(int k=0;k<=20;k++) F[i][j][k]={-1,-1};
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=pre;j<i;j++) if(__builtin_popcount(A[i]&A[j])==B[i]&&dp[i]<dp[j]+1) dp[i]=dp[j]+1,trace[i]=j;
for(int j=0;j<1024;j++)
{
int res=B[i]-__builtin_popcount((j<<10)&A[i]);
if(res<0) continue;
if(dp[i]<F[j][A[i]&1023][res].first+1) dp[i]=F[j][A[i]&1023][res].first+1,trace[i]=F[j][A[i]&1023][res].second;
}
if(i%sqr==0)
{
for(int j=pre;j<=i;j++) for(int k=0;k<1024;k++)
F[A[j]>>10][k][__builtin_popcount(k&A[j])]=max(F[A[j]>>10][k][__builtin_popcount(k&A[j])],{dp[j],j});
pre=i+1;
}
}
int ans=0,pos=0;
for(int i=1;i<=n;i++) if(ans<dp[i]) ans=dp[i],pos=i;
cout<<ans<<"\n";
vector<int> vi;
while(ans--) vi.push_back(pos),pos=trace[pos];
reverse(vi.begin(),vi.end());
for(auto v:vi) cout<<v<<" ";
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |