Submission #1294562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294562		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 = 257;
  v<v<int>> dp(n + 1, v<int>(mx, 1));
  v<v<ll>> pr(n + 1, v<ll>(mx, -1));
  vector<ll> last(mx + 1, -1);
  set<ll> idx_in;

  ll st_idx = 0, ans = 0;
  lp(i, 1, n + 1) {
    dp[i] = dp[i - 1];
    pr[i] = pr[i - 1];
    ll val = a[i - 1];

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

    if (ans < dp[i][val]) {
      ans = dp[i][val];
      st_idx = i;
    }

    if (last[i] == -1) {
    } else {
      ll idxr = last[i];
      idx_in.erase(idxr);
    }
    idx_in.insert(i);
    last[val] = i;
  }

  cout << ans << "\n";

  v<ll> ansi;

  while (st_idx >=1) {
    ansi.push_back(st_idx);
    st_idx = pr[st_idx][a[st_idx - 1]];
  }
  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