Submission #1294571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294571		LIA	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	344 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)
#define pll pair<ll, ll>
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 mx = 259;
  v<int> dp(mx, 0);
  v<ll> pr(mx, -1);
  vector<ll> last(mx + 1, -1);
  set<ll> idx_in;
  v<ll> par_idx(n + 1, -1);

  ll st_idx = 0, ans = 0;
  lp(i, 1, n + 1) {
    ll val = a[i - 1];
    int cur = 1;
    ll par = -1;
    lp(Pval, 0, mx) {
      if (pr[Pval] == -1)
        continue;
      ll cnt = __builtin_popcount(Pval & val);
      if (cnt == k[i - 1]) {
        if (cur < dp[Pval] + 1) {
          cur = dp[Pval] + 1;
          par = pr[Pval];
        }
      }
    }
    par_idx[i] = par;
    if (dp[val] < cur) {
      dp[val] = cur;
      pr[val] = i;
    }
    if (ans < cur) {
      ans = cur;
      st_idx = i;
    }
  }
  cout << ans << "\n";
  v<ll> ansi;

  while (st_idx >= 1) {
    ansi.push_back(st_idx);
    st_idx = par_idx[st_idx];
  }
  reverse(ansi.begin(), ansi.end());
  for (auto it : ansi) {
    cout << it << " ";
  }
}

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