Submission #1294569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294569		LIA	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	444 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 = 300;
  v<int> dp(mx, 1);
  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;

    for (auto idx : idx_in) {
      ll num = a[idx - 1];
      ll cnt = __builtin_popcount(num & val);
      if (cnt == k[i - 1]) {
        if (cur < dp[num] + 1) {
          cur = dp[num] + 1;
          par = idx;
        }
      }
    }

    par_idx[i] = par;

    if (ans < cur) {
      ans = cur;
      st_idx = i;
    }

    if (last[val] != -1) {
      ll idxr = last[val];
      idx_in.erase(idxr);
    }
    idx_in.insert(i);
    last[val] = i;
    if (dp[val] < cur) {
      dp[val] = cur;
      pr[val] = 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