Submission #348772

#	Time	Username	Problem	Language	Result	Execution time	Memory
348772		SeDunion	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6062 ms	10908 KiB

subsequence

#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 << " ";
}

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