Submission #885232

#	Time	Username	Problem	Language	Result	Execution time	Memory
885232		alex_2008	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	54 ms	6284 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], k[N], dp[N];
int last[500];
int bitCount[(1 << 20)];
int way[N];
void precalc() {
	bitCount[0] = 0;
	for (int i = 1; i < (1 << 20); i++) {
		bitCount[i] = bitCount[i / 2] + (i % 2);
	}
}
int main() {
	precalc();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> k[i];
	}
	if (n <= 5000) {
		dp[0] = 1;
		way[0] = -1;
		for (int i = 1; i < n; i++) {
			dp[i] = 1;
			way[i] = -1;
			for (int j = i - 1; j >= 0; j--) {
				if (bitCount[(a[i] & a[j])] == k[i] && dp[i] < dp[j] + 1)  {
					dp[i] = dp[j] + 1;
					way[i] = j;
				}
			}
		}
		int mxdp_ind = 0;
		for (int i = 1; i < n; i++) {
			if (dp[i] > dp[mxdp_ind]) {
				mxdp_ind = i;
			}
		}
		vector <int> ans;
		int ind = mxdp_ind;
		while (ind != -1) {
			ans.push_back(ind + 1);
			ind = way[ind];
		}
		cout << (int)ans.size() << "\n";
		reverse(ans.begin(), ans.end());
		for (int num : ans) {
			cout << num << " ";
		}
	}
	else {
		for (int i = 0; i < 256; i++) {
			last[i] = -1;
		}
		dp[0] = 1;
		way[0] = -1;
		last[a[0]] = 0;
		for (int i = 1; i < n; i++) {
			dp[i] = 1;
			way[i] = -1;
			for (int j = 0; j < 256; j++) {
				if (last[j] == -1) continue;
				if (bitCount[(j & a[i])] != k[i]) continue;
				if (dp[last[j]] + 1 > dp[i]) {
					dp[i] = dp[last[j]] + 1;
					way[i] = last[j];
				}
			}
			last[a[i]] = i;
		}
		int mxdp_ind = 0;
		for (int i = 1; i < n; i++) {
			if (dp[i] > dp[mxdp_ind]) {
				mxdp_ind = i;
			}
		}
		vector <int> ans;
		int ind = mxdp_ind;
		int cnt = 10;
		while (ind != -1) {
			ans.push_back(ind + 1);
			ind = way[ind];
		}
		cout << (int)ans.size() << "\n";
		reverse(ans.begin(), ans.end());
		for (int num : ans) {
			cout << num << " ";
		}
	}
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:83:7: warning: unused variable 'cnt' [-Wunused-variable]
   83 |   int cnt = 10;
      |       ^~~

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