Submission #1164558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164558		ghostlywalrus	Longest beautiful sequence (IZhO17_subsequence)	C++20	7 / 100	18 ms	17988 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
	
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define int long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())

const int maxp = 20;
PI as[1<<maxp];
PI sum[21][1<<maxp];

const int INF = 1e9;
const int MAX_BUFFER = 4000; 

void build(){
	for (int i = 0; i <= 20; ++i)
		for (int j = 0; j < (1<<20); ++i) sum[i][j] = {-INF, -1};

	for (int j = 0; j < (1<<20); ++j) sum[__builtin_popcountll(j)][j] = as[j];

	for (int u = 0; u < 20; ++u)
		for (int i = 0; i < (1<<20); ++i) if (i & (1<<u)){
	 		int j = i ^ (1<<u);
			int v = __builtin_popcountll(i >> (u+1));
			for (int k = v; k <= 20; ++k){
				sum[k][j] = max(sum[k][j], sum[k-v][i]);  
				sum[k][i] = max(sum[k][i], sum[k-v][j]);
			}
		}
}

vector<pair<int, PI>> buffer;

void update(int pos, int val, int id){
	 PI og = as[pos];
	 as[pos] = max(as[pos], {val, id});
	 if (og == as[pos]) return;
	 buffer.pb({id, {pos, val}});
	 if (szo(buffer) >= MAX_BUFFER) {
	 	buffer.clear();
		build();
	 }
}

PI query(int a, int k){
	 PI v1 = sum[k][a];
	 for (auto [id, cur] : buffer){
	 	auto [pos, val] = cur;
	 	if (__builtin_popcountll(pos & a) == k) v1 = max(v1, {val, id});
	 }
	 return v1;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
	int n; cin >> n;
	vector<int> nums(n);
	vector<int> ks(n);
	for (int i = 0; i < n; ++i) cin >> nums[i];
	for (int i = 0; i < n; ++i) cin >> ks[i];
	for (int i = 0; i < (1<<20); ++i) as[i] = {-INF, -1};

	vector<int> dp(n);
	vector<int> last(n);
    
	for (int i = 0; i < n; ++i){
		PI q = query(nums[i], ks[i]);
		last[i] = q.s;
	 	dp[i] = max(1ll, q.f + 1); 
		update(nums[i], dp[i], i);
	}
	
	int ans = 0;
	int id = -1;
	for (int i = 0; i < n; ++i) {
		if (dp[i] >= ans){
	 		ans = dp[i];
			id = i;
		}
	}

	vector<int> resp;
	resp.pb(id+1);
	ans--;
	while (ans--){
	 	id = last[id];	
		resp.pb(id+1);
	}

	reverse(resp.begin(), resp.end());
	cout << szo(resp) << '\n';
	for (auto v : resp) cout << v << " ";
	cout << '\n';

    return 0;
}

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