Submission #1294542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294542		LIA	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	432 KiB

subsequence

// Created by liasa on 23/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (int i = s; i < e; ++i)

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  v<int> a(n), k(n);
  lp(i, 0, n) cin >> a[i];
  lp(i, 0, n) cin >> k[i];

  int ans = 0, idx = -1;
  ll mx = (1LL << 8);
  v<int> dp(mx, 0), pr(mx, -1);
  set<ll> in;
  v<int> parent(n, -1);

  lp(i, 0, n) {
    int val = a[i];
    int best_len = 1;
    int best_prev = -1;

    for (auto it : in) {
      int x = it;
      int cnt = __builtin_popcount(x & val);
      if (cnt == k[i] && dp[x] + 1 > best_len) {
        best_len = dp[x] + 1;
        best_prev = pr[x];
      }
    }
    parent[i] = best_prev;
    if (best_len > dp[val]) {
      dp[val] = best_len;
      pr[val] = i;
    }

    in.insert(a[i]);

    if (best_len > ans) {
      ans = best_len;
      idx = i;
    }
  }

  v<int> vec;
  while (idx != -1) {
    vec.push_back(idx + 1);
    idx = parent[idx];
  }

  cout << ans << '\n';
  reverse(vec.begin(), vec.end());
  for (auto it : vec)
    cout << it << " ";
}

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