제출 #714151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714151		egregious	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	54 ms	2468 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int B = 8;
vector<int> and_mp[1 << B][B + 1]; 
// and_mp[x][i] -> all numbers y s.t. x & y has i set bits
int n, a[N], k[N], dp[N], ind[1 << B], prv[N]; 
// ind[i] = current latest j s.t. a[j] = i
// prv[i] = optimal index to include right before i

int main() {
	// preprocess
	for (int i = 0; i < (1 << B); i++) {
		for (int j = 0; j < (1 << B); j++) {
			and_mp[i][__builtin_popcount(i & j)].push_back(j);
		}
	}

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> k[i];
	}
	fill(dp, dp + n, 1);
	fill(ind, ind + (1 << B), -1);
	if (a[0] < (1 << B)) ind[a[0]] = 0;
	int ans = 1, best_i = 0;
	for (int i = 1; i < n; i++) {
		int best_prv = i;
		if (n <= 5000) {
			for (int j = 0; j < i; j++) {
				if (__builtin_popcount(a[j] & a[i]) == k[i]) {
					if (dp[j] + 1 > dp[i]) {
						best_prv = j;
						dp[i] = dp[j] + 1;
					}
				}
			}
		}
		else {
			for (int prev : and_mp[a[i]][k[i]]) {
				if (ind[prev] >= 0 && dp[ind[prev]] + 1 > dp[i]) {
					best_prv = ind[prev];
					dp[i] = dp[ind[prev]] + 1;
				}
			}
		}
		prv[i] = best_prv;
		if (dp[i] > ans) {
			ans = dp[i];
			best_i = i;
		}
		if (a[i] < (1 << 8)) ind[a[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