Submission #1133552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133552		JelalTkm	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	57 ms	3908 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<vector<int>> d(257, vector<int> ());
      d[a[0]].push_back(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 ((int) d[j].size() && cnt == k[i]) {
            dp[i] = max(dp[i], dp[d[j].back()] + 1);
          }
        }
        d[a[i]].push_back(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 (true) {
          bool ok = 0;
          asq.push_back(i + 1);
          for (int j = 0; j <= 256; j++) {
            int an = (a[i] & j);
            int cnt = __builtin_popcountll(an);
            int l = lower_bound(d[j].begin(), d[j].end(), i) - d[j].begin();
            l--;
            if (l >= 0 && (int) d[j].size() && cnt == k[i] && dp[i] == dp[d[j][l]] + 1) {
              i = d[j][l];
              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';
      }
    }
  }

  return 0;
}

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