#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#define hyathu main
#define popcorn __builtin_popcount
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr int mmsb = 1e5 + 69, mmb = 1029, mmn = 20, bit = 10;
const ld pi = atan(1) * 4;
/*
Sub 1 (n <= 15): Backtrack (Nothing to say)
Sub 2 (n <= 5000):
Goi dp[i] = max LSB tu 1...n -> dp[i] = dp[j] + 1 : popcorn(a[i] & a[j]) = k[i]
-> O(n^2) (still easy)
Sub 3 (n <= 1e5, a[i] <= 2^8):
Cach 1:
Goi dp[i][x] = max LSB tu 1...n, ket thuc bang so x -> dp[i][a[i]] = dp[i - 1][j] + 1 : popcorn(a[i], j) = k[i]
Co the bo di mot chieu do dp[i] chi phu thuoc vao dp[i - 1]
-> O(n * m) (m = max(a[i]))
Cach 2:
dp[x] nhu tren mat O(m) de for qua cac x
-> Them mot chieu dp
-> dp[x][k] = max(dp[x'] : bitcount(x' & x) = k)
-> Xet den a[i], ans[i] = dp[a[i]][k[i]], cap nhat lai cho moi dp[y][bitcount(a[i], y)] = max(dp[y][bitcount(a[i], y)], ans[i])
Van la O(n * m)
Sub 4:
Cach 1 cua sub 3: O(m) cap nhat ket qua, O(1) cap nhat cac trang thai
Cach 2 cua sub 3: O(1) cap nhat ket qua, O(m) cap nhat cac trang thai
Van chua du tot -> Can chia ra 2 phan.
Xet den so a[i], chia ra phan ben trai co b bit, phan ben phai co 20 - b bit.
Goi phan ben trai la lx, ben phai la rx
Can doi trang thai dp:
Khi xet den x,
goi dp[i][rx(x)][k] = l.
i = lx cua so truoc do
bitcount(rx, j) = k (j la rx cua so truoc do)
l = max len
-> ans[i] = dp[i'][rx(a[i])][k[i] - bitcount(a[i], i')] + 1 (voi moi i' tu 0...2^b)
Do can biet voi moi j co phan ben trai la i', phan ben phai giao voi rx(a[i]) k bit thi max la bao nhieu
-> Do phuc tap O(2^b)
Da tinh xong ans, gio can cap nhat dp.
-> a[i] co phan ben trai la lx(a[i])
-> cap nhat tat ca dp[lx(a[i])]
for tat ca gia tri co the cua phan ben phai, goi la r
-> maximize(dp[lx(a[i])][r][bitcount(r, rx(a[i]))], ans[i])
-> Do phuc tap O(2^b)
Can can bang giua 2 viec cap nhat dap an va cap nhat trang thai dp -> Chon b = 1/2 * maxbit la tot nhat -> b = 10.
Dieu quan trong cua bai nay: dp khong phai la cho vi tri i, ma la cho gia tri
-> chia thanh 2 viec: Cap nhat ket qua cho vi tri i, va cap nhat lai bang dp
-> co the chia ra de do phuc tap giam xuong sqrt
Mot so luu y ve cai dat:
+, Su dung mang prv de backtrack cho de
+, Su dung struct de luu thong tin cho de nhin
*/
struct info{
int len = 0, idx = 0;
};
int n;
info dp[mmb][mmb][mmn];
int a[mmsb], k[mmsb], ans[mmsb], prv[mmsb];
void readData(){
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = 1; i <= n; ++i)
cin >> k[i];
}
inline int L(int x){
return (x >> bit) & ((1 << bit) - 1);
}
inline int R(int x){
return x & ((1 << bit) - 1);
}
inline int I(int x, int y){
return popcorn(x & y);
}
inline bool maxi(int &a, int b){
if(a < b){
a = b;
return 1;
}
return 0;
}
void solve(){
int res = 0, cur = 0;
for(int i = 1; i <= n; ++i){
//getting ans
int rx = R(a[i]);
for(int lf = 0; lf < (1 << bit); ++lf){
int rem = k[i] - I(L(a[i]), lf);
const info &p = dp[lf][rx][rem];
if(maxi(ans[i], p.len))
prv[i] = p.idx;
}
++ans[i];
if(ans[i] > res){
res = ans[i];
cur = i;
}
//updating dp
int lx = L(a[i]);
for(int rt = 0; rt < (1 << bit); ++rt){
int cnt = I(rx, rt);
info &p = dp[lx][rt][cnt];
if(p.len < ans[i]){
p.len = ans[i];
p.idx = i;
}
}
}
cout << res << "\n";
stack <int> st;
while(cur != 0){
st.push(cur);
cur = prv[cur];
}
while(!st.empty()){
cout << st.top() << " ";
st.pop();
}
}
#define filename "test"
int hyathu(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifdef dangheo
freopen("test.inp", "r", stdin);
//freopen("test.out", "w", stdout);
#else
//freopen(filename".INP", "r", stdin);
//freopen(filename".OUT", "w", stdout);
#endif
readData();
solve();
return 0;
}
