Submission #757866

#	Time	Username	Problem	Language	Result	Execution time	Memory
757866		shadow_sami	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	468 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int B = 8;
struct State {
	int len, end;
};
int main() {
	// preprocess:
	// bc[i][j] = bit_count(i & j)
	vector<vector<int>> bc(1 << B, vector<int>(1 << B));
	for (int i = 0; i < (1 << B); i++) {
		for (int j = 0; j < (1 << B); j++) {
			bc[i][j] = __builtin_popcount(i & j);
		}
	}

	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<int> k(n);
	for (int i = 0; i < n; i++) cin >> k[i];
	int ans = 1;
	// best_i: most optimal index to end on
	int best_i = 0;
	vector<int> prv(n);               // prv[i]: best index to include before i
	iota(prv.begin(), prv.end(), 0);  // prv[i] = i

	vector<State> dp1(1 << B, State{-1, -1});
	for (int i = 0; i < n; i++) {
		if (dp1[a[i]].len == -1) {
			dp1[a[i]].len = 1;
			dp1[a[i]].end = i;
		}
		for (int j = 0; j < (1 << B); j++) {
			if (bc[j][a[i]] == k[i] && dp1[j].len + 1 > dp1[a[i]].len) {
				dp1[a[i]].len = dp1[j].len + 1;
				dp1[a[i]].end = i;
				prv[i] = dp1[j].end;
			}
		}
		if (dp1[a[i]].len > ans) {
			ans = dp1[a[i]].len;
			best_i = i;
		}
	}

	cout << ans << endl;

	vector<int> res;
	while (prv[best_i] != best_i) {
		res.push_back(best_i);
		best_i = prv[best_i];
	}
	res.push_back(best_i);
	reverse(res.begin(), res.end());
	for (int x : res) { cout << x + 1 << " "; }
}

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