Submission #404463

#TimeUsernameProblemLanguageResultExecution timeMemory
404463rama_pangLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
4045 ms183544 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }

  const int LOG = 20;
  vector<pair<int, int>> dp(N);
  vector<vector<pair<int, int>>> opt(LOG + 1, vector<pair<int, int>>(1 << LOG, {-1, -1}));

  vector<int> popcount(1 << LOG);
  for (int i = 0; i < (1 << LOG); i++) {
    popcount[i] = __builtin_popcount(i);
  }

  for (int i = 0; i < N; i++) {
    dp[i] = {1, -1};
    int upperMe = A[i] >> (LOG / 2);
    int lowerMe = A[i] - (upperMe << (LOG / 2));
    for (int upper = 0; upper < (1 << (LOG / 2)); upper++) {
      int need = B[i] - popcount[upperMe & upper];
      if (0 <= need && need < LOG) {
        auto &v = opt[need][(upper << (LOG / 2)) + lowerMe];
        dp[i] = max(dp[i], {1 + v.first, v.second});
      }
    }
    for (int lower = 0; lower < (1 << (LOG / 2)); lower++) {
      auto &v = opt[popcount[lowerMe & lower]][(upperMe << (LOG / 2)) + lower];
      v = max(v, {dp[i].first, i});
    }
  }

  vector<int> ans;
  int i = max_element(begin(dp), end(dp)) - begin(dp);
  while (i != -1) {
    ans.emplace_back(i);
    i = dp[i].second;
  }

  reverse(begin(ans), end(ans));
  cout << ans.size() << '\n';
  for (auto a : ans) {
    cout << a + 1 << ' ';
  }
  cout << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...