Submission #486665

#	Time	Username	Problem	Language	Result	Execution time	Memory
486665		ez_ioi	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	263 ms	262144 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

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

set <pair <int, pair <int, int> > > st[(1 << 11)][(1 << 11)];

int mask1[mxN], mask2[mxN];

int main() {
	ios :: sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	vector <int> f, s;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		for (int j = 0; j < 10; ++j) {
			if ((a[i] >> j) & 1) mask1[i] += (1 << j);
		}
		for (int j = 10; j < 20; ++j) {
			if ((a[i] >> j) & 1) mask2[i] += (1 << j);
		}
		f.push_back(mask1[i]); s.push_back(mask2[i]);
	}
	for (int i = 1; i <= n; ++i) cin >> k[i];
	sort(f.begin(), f.end());
	f.erase(unique(f.begin(), f.end()), f.end());
	sort(s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	pair <int, int> ans = {0, 0};
	for (int i = 1; i <= n; ++i) {
		dp[i] = 1;
		{ // get
			for (auto mask : f) {
				int x = k[i] - __builtin_popcount(mask1[i] & mask);
				if (st[mask][(mask2[i] << 10)].empty()) continue;
				auto up = st[mask][(mask2[i] << 10)].lower_bound({x + 1, {0, 0}});
				if (up == st[mask][(mask2[i] << 10)].begin()) continue;
				--up;
				if (up -> first == x) {
					pair <int, int> y = up -> second;
					if (y.first + 1 > dp[i]) {
						p[i] = y.second;
						dp[i] = y.first + 1;
					}
				}
			}
		}
		{ // upd
			for (auto mask : s) 
				st[mask1[i]][(mask << 10)].insert({__builtin_popcount(mask & mask2[i]), {dp[i], i}});
		}
		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;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60