Submission #1269066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269066		lmduc270410	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	6092 ms	4560 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 1e5 + 5, M = 2e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;

int n, a[N], k[N];
short pcnt[M];
pii dp[N];
int d[25][N], c[25], idk[N];

void solve(){
	
	cin>>n;
	for(int i = 1; i <= n; i++) cin>>a[i];
	for(int i = 1; i <= n; i++) cin>>k[i];
	for(int i = 1; i <= (1 << 20); i++) pcnt[i] = __builtin_popcount(i);

	pii ans = {0, 0};
	for(int i = 1; i <= n; i++){
		dp[i] = {1, i};
		int cb = pcnt[a[i]];
		// cout<<i<<" "<<a[i]<<" "<<cb<<" "<<k[i]<<'\n';
		if(cb < k[i]){
			ans = max(ans, {1, i});
			d[cb][++c[cb]] = i;
			continue;
		}
		for(int v = k[i]; v <= 20; v++){
			for(int t = 1; t <= c[v]; t++){
				int j = d[v][t];
				if(pcnt[(a[i] & a[j])] == k[i]){
					dp[i] = max(dp[i], {dp[j].fi + 1, j});
				}
			}
		}
		ans = max(ans, {dp[i].fi, i});
		d[cb][++c[cb]] = i;
	}

	// for(int i = 1; i <= n; i++) cout<<"!!! "<<dp[i].fi<<" "<<dp[i].se<<'\n';

	cout<<ans.fi<<'\n';
	int m = 0, cur = ans.se;
	while(dp[cur].se != cur){
		idk[++m] = cur;
		cur = dp[cur].se;
	}
	idk[++m] = cur;
	reverse(idk + 1, idk + m + 1);
	for(int i = 1; i <= m; i++) cout<<idk[i]<<" ";
}

signed main(){
	
	// freopen(".inp", "r", stdin);
	// freopen(".out", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int tc = 1;
	// cin>>tc;
	while(tc--) solve();
}

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