#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int)(x).size()
const int LG = 10;
int popcnt[1 << LG][1 << LG];
inline void solve(){
int n;
cin >> n;
vi a(n), k(n);
for(int &i : a){
cin >> i;
}
for(int &i : k){
cin >> i;
}
vector<vector<vector<pii>>> dp(1 << LG, vector<vector<pii>>(1 << LG, vector<pii>(LG + 1)));
vi from(n, -1);
int ans = INT32_MIN, lst = -1;
for(int i = 0; i < n; i++){
int le = a[i] >> LG, ri = a[i] % (1 << LG), lbs = 1;
for(int mask = 0; mask < (1 << LG); mask++){
int bc = popcnt[mask][ri];
if(bc > k[i] || k[i] - bc > LG) continue;
if(dp[le][mask][k[i] - bc].fi + 1 > lbs){
from[i] = dp[le][mask][k[i] - bc].se;
lbs = dp[le][mask][k[i] - bc].fi + 1;
}
}
for(int mask = 0; mask < (1 << LG); mask++){
int bc = popcnt[mask][le];
if(lbs > dp[mask][ri][bc].fi){
dp[mask][ri][bc] = {lbs, i};
}
}
if(lbs > ans){
ans = lbs;
lst = i;
}
}
cout << ans << "\n";
vi lbs;
while(from[lst] != -1){
lbs.emplace_back(lst + 1);
lst = from[lst];
}
lbs.emplace_back(lst + 1);
for(int i = sz(lbs) - 1; i >= 0; i--){
cout << lbs[i] << " ";
}
cout << "\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
for(int mask = 0; mask < (1 << LG); mask++){
for(int m = 0; m < (1 << LG); m++){
popcnt[mask][m] = __builtin_popcount(mask & m);
}
}
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
# | 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... |