| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 344158 | IZhO_2021_I_want_Silver | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 0 ms | 0 KiB |
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 <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
typedef pair <int, int> pii;
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define F first
#define S second
const int N = 1e5 + 5;
const int MX = (1 << 8) + 5;
int n, a[N], k[N], pre[N], dp[N], pos[N];
vector <int> vec;
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> k[i];
}
int ans = 0, posans = 0;
for(int i = 1; i <= n; ++i) {
int mx = 0;
if(n <= 5000) {
for(int j = 1; j < i; ++j) {
if(__builtin_popcount((a[i] & a[j])) == k[i]) {
if(mx < dp[j]) {
mx = dp[j];
p[i] = j;
}
}
}
} else {
for(int j = 0; j < (1 << 8); ++j) {
for(int posj : pos[j]) {
if(__builtin_popcount((a[i] & j)) == k[i]) {
if(mx < dp[posj]) {
mx = dp[posj];
p[i] = posj;
}
}
}
}
pos[a[i]].pb(i);
}
dp[i] = mx + 1;
if(ans < dp[i]) {
ans = dp[i];
posans = i;
}
}
vector <int> vec;
while(posans) {vec.pb(posans); posans = p[posans];}
reverse(all(vec));
cout << ans <<'\n';
for(int it : vec)
cout << it <<' ';
return 0;
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tests = 1;
//cin >> tests;
while (tests --) {
solve();
}
return 0;
}
/*
Just Chalish!
4
1 2 3 4
10 0 1 0
2
8 9
20 0
5
5 3 5 3 5
10 1 20 1 20
*/