#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vl vector<ll>
int n;
const int MN = 1e5 + 7, MS = (1<<20)+7, MB = (1<<10)+7, MK = 21;
int a[MN], k[MN], best[MN], prv[MN];
int dp[MB][MB][MK][2]; //dp[l][r][k][0]: for all x with l(x)=l, bitcount(r(x), r) = k,
//the maximum length of an LBS ending at x, dp[l][r][k][1] is the index of this optimal x
int bc[MB][MB]; //bit count of (i&j)
int l[MS], r[MS]; //l[i]: leftmost 10 bits of i, r[i]: rightmost 10 bits of i
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for(int i = 0; i < MB; i++)
for(int j = 0; j < MB; j++) bc[i][j] = __builtin_popcount(i&j);
for(int i = 0; i < MS; i++) {
l[i] = i>>10;
r[i] = i % (1<<10);
}
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> k[i];
for(int i = 1; i <= n; i++) {
for(int lx = 0; lx < (1<<10); lx++) {
if(k[i] < bc[lx][l[a[i]]]) continue;
// if(i == 1 && lx == 2) cout << best[i] << ' ' << r[a[i]] << ' ' << bc[lx][l[a[i]]] << ' ' << dp[lx][r[a[i]]][k[i]-bc[lx][l[a[i]]]][0] << '\n';
int cur = dp[lx][r[a[i]]][k[i]-bc[lx][l[a[i]]]][0];
if(cur+1 > best[i]) {
best[i] = cur+1;
prv[i] = dp[lx][r[a[i]]][k[i]-bc[lx][l[a[i]]]][1];
}
}
for(int y = 0; y < (1<<10); y++) {
if(best[i] > dp[l[a[i]]][y][bc[y][r[a[i]]]][0]) {
dp[l[a[i]]][y][bc[y][r[a[i]]]][0] = best[i];
dp[l[a[i]]][y][bc[y][r[a[i]]]][1] = i;
}
}
}
int mxidx = 1;
for(int i = 1; i <= n; i++) {
// cout << best[i] << ' ';
if(best[i] > best[mxidx]) mxidx = i;
}
cout << best[mxidx] << '\n';
vi ans;
while(mxidx != 0) {
ans.pb(mxidx);
mxidx = prv[mxidx];
}
reverse(ans.begin(), ans.end());
for(int num : ans) cout << num << ' ';
// 4
// 1 2 3 4
// 10 0 1 0
// 5
// 5 3 5 3 5
// 10 1 20 1 20
}
# | 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... |