| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 344158 | IZhO_2021_I_want_Silver | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
*/