This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define bug cout << "bug" << endl
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pll pair <ll, ll>
#define pii pair <int, int>
#define triple pair <pair <ll, ll> , ll>
#define ull unsigned long long
#define ld long double
#define pinode pair <node*, node*>
const ll INF = 9e18 + 5;
const ll inf = 1e9 + 5;
const ll N = 1e5 + 5;
const ll shift = 2e6;
const ll mod = 1e9 + 7;
const ll M = 1024 + 5;
const ll LOG = 21;
const ll sp = 263;
const ll block = 500;
const double eps = 1e-10;
int n, a[N], k[N], len[N], dp[M][M][21], last[N], lg = 10, cnt[M * M];
int main(){
speed;
for(int i = 0; i <= M * M - 5; i++)
cnt[i] = __builtin_popcount(i);
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
cin >> k[i];
memset(dp, -1, sizeof(dp));
for(int i = 1; i <= n; i++){
last[i] = -1;
len[i] = 1;
int firsthalf = 0, secondhalf = 0;
for(int bit = 0; bit < 20; bit++){
if((1 << bit) & a[i]){
if(bit < lg)
firsthalf |= (1 << bit);
else
secondhalf |= (1 << (bit - 10));
}
}
for(int mask = 0; mask < 1024; mask++){
int need = cnt[(mask & firsthalf)] - k[i];
if(0 <= need && need <= lg){
int index = dp[mask][secondhalf][need];
if(index != -1){
if(len[i] < len[index] + 1){
len[i] = len[index] + 1;
last[i] = index;
}
}
}
}
for(int mask = 0; mask < 1024; mask++){
int common = (mask & secondhalf);
int index = dp[firsthalf][mask][common];
if(index == -1 || len[index] < len[i]){
dp[firsthalf][mask][common] = i;
}
}
}
int mx = 0, st;
for(int i = 1; i <= n; i++){
if(mx < len[i]){
mx = len[i];
st = i;
}
}
vector <int> ans;
while(st != -1){
ans.pb(st);
st = last[st];
}
reverse(all(ans));
cout << ans.size() << endl;
for(auto to : ans)
cout << to << " ";
}
/*
%I64d
%I64d
*/
# | 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... |