제출 #1290650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290650		muhammad-ahmad	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	187 ms	8732 KiB

subsequence

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io(){
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(); cout.tie();
	cout << setprecision(9);
}

#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

void solve() {
	int n; cin >> n;
	
	
	int a[n + 1] = {}, k[n + 1] = {};
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> k[i];
	
	int dp[n + 1] = {};
	if (n > 5000){
		map<int, int> B;
		for (int i = 1; i <= n; i++){
			dp[i] = 1;
			for (int j = 0; j < (1LL << 8); j++){
				if (__builtin_popcount(a[i] & j) == k[i]) dp[i] = max(dp[i], B[j] + 1);
			}
			B[a[i]] = max(B[a[i]], dp[i]);
		}
	}
	else {
		for (int i = 1; i <= n; i++){
			dp[i] = 1;
			for (int j = i - 1; j >= 1; j--){
				if (__builtin_popcount(a[i] & a[j]) == k[i]) dp[i] = max(dp[i], dp[j] + 1);
			}
		}	
	}
	
	
	int ma = 0;
	vector<int> ans;
	for (int i = 1; i <= n; i++) if (dp[ma] < dp[i]) ma = i;
	
	ans.push_back(ma);
	
	while (dp[ma] != 1){
		for (int j = ma - 1; j >= 1; j--){
			if (__builtin_popcount(a[ma] & a[j]) == k[ma] && dp[j] + 1 == dp[ma]){
				ans.push_back(j);
				ma = j;
				break;
			}
		}
	}
	
	reverse(all(ans));
	cout << ans.size() << endl;
	for (auto i : ans) cout << i << ' ';
	cout << endl;
	
	return;
}

signed main() {
    fast_io();
    srand(chrono::steady_clock::now().time_since_epoch().count());
    int tc = 1;
    // cin >> tc
    while (tc--) solve();
    return 0;
}

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