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>
#define pb push_back
#define ll long long
#define ld long double
#define f first
#define s second
#define mp make_pair
const ll maxn = 2e6 + 100, maxm = 11, maxk = (1 << 10);
const ll inf = 1000000000, mod = inf + 7, mod2 = 998244353;
const ll pa = 31, block = 400;
using namespace std;
int n;
int a[maxn], k[maxn], len[maxn], last[maxn], dp[maxk][maxk][maxm], cnt[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
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 <= maxn - 1; ++i){
cnt[i] = __builtin_popcount(i);
}
for (int i = 1; i <= n; ++i){
int f = 0, s = 0;
for (int j = 0; j < 10; ++j){
if ((1 << j) & a[i]){
f |= (1 << j);
}
if ((1 << (j + 10)) & a[i]){
s |= (1 << j);
}
}
len[i] = 1;
for (int j = 0; j < maxk; ++j){
int need = k[i] - cnt[j & f];
if (need >= 0 && need < maxm){
int pos = dp[j][s][need];
if (len[pos] + 1 > len[i]){
len[i] = len[pos] + 1;
last[i] = pos;
}
}
}
for (int j = 0; j < maxk; ++j){
int x = cnt[j & s];
int ind = dp[f][j][x];
if (len[ind] < len[i]){
dp[f][j][x] = i;
}
}
}
int pos = 0;
for (int i = 1; i <= n; ++i){
if (len[pos] < len[i]){
pos = i;
}
}
vector<int> v;
while (pos > 0){
v.pb(pos);
pos = last[pos];
}
cout << v.size() << '\n';
reverse(v.begin(), v.end());
for (auto it : v){
cout << it << " ";
}
}
# | 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... |