제출 #714140

#제출 시각아이디문제언어결과실행 시간메모리
714140egregiousLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
3 ms1236 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int B = 8;
vector<int> and_mp[1 << B][B]; // 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);
	ind[a[0]] = 0;
	int ans = 1, best_i = 0;
	for (int i = 1; i < n; i++) {
		int best_prv = i;
		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;
		}
		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 << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...