Submission #1130932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130932		mnbvcxz123	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	52 ms	1860 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() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin>>n;
  if(n>5000){
	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); }
	}

	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;
	int best_i = 0;
	vector<int> prv(n);
	iota(prv.begin(), prv.end(), 0);

	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 << " "; }
  }else{
      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]; }

	vector<int> dp(n, 1);
	int ans = 1;
	int best_i = 0;
	vector<int> prv(n);
	iota(prv.begin(), prv.end(), 0);

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (__builtin_popcount(a[j] & a[i]) == k[i]) {
				if (dp[j] + 1 > dp[i]) {
					prv[i] = j;
					dp[i] = dp[j] + 1;
				}
			}
		}
		if (dp[i] > ans) {
			ans = dp[i];
			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: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60