제출 #348772

#제출 시각아이디문제언어결과실행 시간메모리
348772SeDunionLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6062 ms10908 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 3;

int a[N], k[N], fh, sh, ki;
const int LOG = 20;
const int HALF = LOG >> 1; // 10

int l[LOG], v[LOG][N], uf[1 << LOG], us[1 << LOG], I = 1;

pair<int,int> dp[N], mr[1 << HALF][1 << HALF];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0 ; i < n ; ++ i) cin >> a[i];
	for (int i = 0 ; i < n ; ++ i) cin >> k[i];
	for (int i = 0 ; i < n ; ++ i) {
		fh = sh = 0;
		dp[i] = {0, i};
		for (int j = 0 ; j < HALF ; ++ j) fh += (1 << j) & a[i];
		for (int j = HALF ; j < LOG ; ++ j) sh += ((1 << j) & a[i]) >> HALF;
		//cout << fh << " " << sh << " fsh\n";
		if (k[i] != LOG) {
			for (int j = 0 ; j < LOG ; ++ j) l[j] = 0;
			for (int mask = 0 ; mask < (1 << HALF) ; ++ mask) {
				ki = __builtin_popcount(mask & fh);
				if (uf[mask])
					v[ki][l[ki]++] = mask;
			}
			for (int mask = 0 ; mask < (1 << HALF) ; ++ mask) {
				ki = __builtin_popcount(mask & sh);
				if (!us[mask] || ki > k[i]) continue;
				ki = k[i] - ki;
				for (int j = 0 ; j < l[ki] ; ++ j)
					dp[i] = max(dp[i], mr[v[ki][j]][mask]);
			}
		}
		dp[i].first++;
		mr[fh][sh] = max(mr[fh][sh], {dp[i].first, i});
		uf[fh] = 1;
		us[sh] = 1;
		//cout << i << " " << dp[i].first << " " << dp[i].second << " dpi\n";
		if (dp[I].first < dp[i].first) I = i;
	}
	cout << dp[I].first << "\n";
	l[0] = 0;
	while(1) {
		v[0][l[0]++] = I;
		if (I == dp[I].second)break;
		I = dp[I].second;
	}
	while (--l[0] >= 0) cout << v[0][l[0]] + 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...