제출 #348776

#제출 시각아이디문제언어결과실행 시간메모리
348776SeDunionLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
1 ms364 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
const int F[] = {0, 3, 4, 1, 9, 19, 15, 6, 16, 12};
const int S[] = {2, 5, 17, 8, 18, 11, 13, 14, 7, 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 << F[j]) & a[i])) << j, sh += (!!((1 << S[j]) & a[i])) << j;
		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...