# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1269097 | tryharderforioi100 | Longest beautiful sequence (IZhO17_subsequence) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i=0;i<n;i++) cin >> a[i];
for (int i=0;i<n;i++) cin >> b[i];
vector<int> dp(n, 1), parent(n, -1);
vector<int> best(33, 0), bestIdx(33, -1);
int ans = 1, last = 0;
for (int i=0;i<n;i++) {
dp[i] = best[b[i]] + 1;
if (bestIdx[b[i]] != -1) parent[i] = bestIdx[b[i]];
if (dp[i] > best[__builtin_popcount(a[i])]) {
best[__builtin_popcount(a[i])] = dp[i];
bestIdx[__builtin_popcount(a[i])] = i;
}
if (dp[i] > ans) {
ans = dp[i];
last = i;
}
}
cout << ans << "\n";
vector<int> seq;
for (int x = last; x != -1; x = parent[x]) seq.push_back(x+1);
reverse(seq.begin(), seq.end());
for (int x: seq) cout << x << " ";
cout << "\n";
}