제출 #486645

#제출 시각아이디문제언어결과실행 시간메모리
486645ez_ioiLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
97 ms10488 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int mxN = 3e6 + 5, mod = 1e9 + 7, LOG = 20;

int n, a[mxN], k[mxN], dp[mxN], p[mxN];

pair <int, int> d[mxN];

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> k[i];
	if (n <= 5000) {
		pair <int, int> ans = {0, 0};
		for (int i = 1; i <= n; ++i) {
			dp[i] = 1;
			for (int j = i - 1; j > 0; j--) {
				if (__builtin_popcount((a[i] & a[j])) == k[i]) {
					if (dp[j] + 1 > dp[i]) {
						dp[i] = dp[j] + 1;
						p[i] = j;
					}
				}
			}
			ans = max(ans, {dp[i], i});
		}
		cout << ans.first << '\n';
		int now = ans.second;
		vector <int> seq;
		while (now) { seq.push_back(now); now = p[now]; }
		reverse(seq.begin(), seq.end());
		for (auto x : seq) cout << x << ' ';
		return 0;
	}
	pair <int, int> ans = {0, 0};
	for (int i = 1; i <= n; ++i) {
		if (!d[a[i]].first) d[a[i]] = {1, i};
		for (int j = 0; j < (1 << 8); ++j) {
			if (__builtin_popcount((a[i] & j)) == k[i]) {
				if (d[j].second != i && d[j].first + 1 > d[a[i]].first) {
					p[i] = d[j].second;
					d[a[i]] = {d[j].first + 1, i};
				}
			}
		}
		ans = max(ans, d[a[i]]);
	}
	cout << ans.first << '\n';
	int now = ans.second;
	vector <int> seq;
	while (now) { seq.push_back(now); now = p[now]; }
	reverse(seq.begin(), seq.end());
	for (auto x : seq) cout << x << ' ';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...