Submission #1294701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294701		LIA	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	5 ms	4696 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>
struct State {
  int len, end;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int mx = 1024;
  v<v<int>> ba(mx, v<int>(mx));
  lp(i, 0, mx) {
    lp(j, 0, mx) { ba[i][j] = __builtin_popcount(i & j); }
  }
  v<int> a(n), k(n);
  lp(i, 0, n) cin >> a[i];
  lp(i, 0, n) cin >> k[i];
  int ans = 1;
  v<int> pr(n);
  iota(pr.begin(), pr.end(), 0);
  vector<vector<State>> dp(mx, vector<State>(11, State{0, -1}));
  int best_idx = 0;
  lp(i, 0, n) {
    int len = 1;
    if (k[i] <= 10 && dp[a[i]][k[i]].len > 0) {
      len = dp[a[i]][k[i]].len + 1;
      pr[i] = dp[a[i]][k[i]].end;
    }
    lp(j, 0, mx) {
      int t = ba[a[i]][j];
      State &AS = dp[j][t];
      if (len > AS.len) {
        AS = State{len, i};
      }
    }
    if (len > ans) {
      ans = len;
      best_idx = i;
    }
  }
  cout << ans << '\n';
  v<int> res;
  while (pr[best_idx] != best_idx) {
    res.push_back(best_idx);
    best_idx = pr[best_idx];
  }
  res.push_back(best_idx);
  reverse(res.begin(), res.end());
  for (int x : res) {
    cout << x + 1 << " ";
  }
}

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