Submission #476897

#	Time	Username	Problem	Language	Result	Execution time	Memory
476897		ntabc05101	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4197 ms	48200 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;

#define taskname ""

const int mxN = 100000;
const int mxK2 = 10;

int n;
int a[mxN + 1], k[mxN + 1];
array<int, 2> dp[mxN + 1];
int trc[1 << mxK2][1 << mxK2][mxK2 + 1];

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  else {
    if (fopen(taskname".in", "r")) {
      freopen(taskname".in", "r", stdin);
      freopen(taskname".out", "w", stdout);
    }
  }

  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> k[i];
  }
  memset(trc, -1, sizeof(trc));

  array<int, 2> res{0, -1};
  for (int i = 0; i < n; i++) {
    int msk1 = a[i] & ((1 << mxK2) - 1), msk2 = a[i] >> mxK2;
    dp[i] = {1, -1};
    for (int pmsk1 = 0; pmsk1 < (1 << mxK2); pmsk1++) {
      int dff1 = __builtin_popcount(pmsk1 & msk1);
      int dff2 = k[i] - dff1;
      if (dff2 < 0 || dff2 > mxK2) {
        continue;
      }
      int prv = trc[pmsk1][msk2][dff2];
      if (~prv) {
        dp[i] = max(dp[i], {dp[prv][0] + 1, prv});
      }
    }

    res = max(res, {dp[i][0], i});

    for (int nmsk2 = 0; nmsk2 < (1 << mxK2); nmsk2++) {
      int dff2 = __builtin_popcount(nmsk2 & msk2);
      auto &nxt = trc[msk1][nmsk2][dff2];
      if (nxt == -1 || dp[nxt][0] < dp[i][0]) {
        nxt = i;
      }
    }
  }

  cout << res[0] << "\n";
  vector<int> lst;
  while (~res[1]) {
    lst.push_back(res[1]);
    res = dp[res[1]];
  }
  for (int i = lst.size() - 1; ~i; i--) {
    cout << 1 + lst[i] << " ";
  }

  cout << "\n";

  return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:21:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |       freopen(taskname".in", "r", stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:22:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |       freopen(taskname".out", "w", stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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