Submission #1133555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133555		JelalTkm	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	33 ms	3396 KiB

subsequence

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 3e5 + 10;
const int md = 1e9 + 7;
const int INF = 1e18;

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for (int i = 0; i < n; i++)
      cin >> a[i];
    for (int i = 0; i < n; i++)
      cin >> k[i];

    if (n <= 5000) {
      vector<int> dp(n + 1);
      for (int i = 1; i < n; i++) {
        for (int j = i - 1; j >= 0; j--) {
          int an = (a[i] & a[j]);
          int cnt = __builtin_popcountll(an);
          // cout << a[i] << " " << a[j] << " " << an << " " << cnt << " " << (cnt == k[i]) << '\n';
          if (cnt == k[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
          }
        }
      }
      int ans = 0, ind;
      for (int i = 0; i < n; i++)
        if (dp[i] > ans)
          ans = dp[i], ind = i;

      if (ans != 0) {
        cout << ans + 1 << '\n';
        vector<int> asq;
        int i = ind;
        while (true) {
          bool ok = 0;
          asq.push_back(i + 1);
          for (int j = i - 1; j >= 0; j--) {
            int an = (a[i] & a[j]);
            int cnt = __builtin_popcountll(an);
            if (dp[i] == dp[j] + 1 && cnt == k[i]) {
              i = j;
              ok = 1;
              break;
            }
          }
          if (!ok)
            break;
        }
        reverse(asq.begin(), asq.end());
        for (auto i : asq)
          cout << i << " ";
        cout << '\n';
      } else {
        cout << 1 << '\n' << 1 << '\n';
      }
    } else {
      vector<int> dp(n + 1);
      vector<pair<int, int>> d(257);
      vector<int> per(n + 1, -1);
      d[a[0]] = {1, 0};
      for (int i = 1; i < n; i++) {
        for (int j = 0; j <= 256; j++) {
          int an = (a[i] & j);
          int cnt = __builtin_popcountll(an);
          // cout << a[i] << " " << j << " " << an << " " << cnt << " " << (int) d[j].size() << " " << (cnt == k[i]) << '\n';
          if (d[j].first && cnt == k[i]) {
            if (dp[i] < d[j].first) {
              dp[i] = d[j].first;
              per[i] = d[j].second;
            }
          }
        }
        if (d[a[i]].first < dp[i] + 1) {
          d[a[i]] = {dp[a[i]] + 1, i};
        }
      }
      int ans = 0, ind;
      for (int i = 0; i < n; i++)
        if (dp[i] > ans)
          ans = dp[i], ind = i;

      if (ans != 0) {
        cout << ans + 1 << '\n';
        vector<int> asq;
        int i = ind;
        while (i != -1) {
          bool ok = 0;
          asq.push_back(i + 1);
          i = per[i];
        }
        reverse(asq.begin(), asq.end());
        for (auto i : asq)
          cout << i << " ";
        cout << '\n';
      } else {
        cout << 1 << '\n' << 1 << '\n';
      }
    }
  }

  return 0;
}

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