Submission #667754

#	Time	Username	Problem	Language	Result	Execution time	Memory
667754		I_love_Chou_Giang	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	92 ms	2120 KiB

subsequence

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

typedef long long ll;

#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

#define R_EP(i, a, b, s) for (int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define R_EP1(e) R_EP(i, 0, e, 1)
#define R_EP2(i, e) R_EP(i, 0, e, 1)
#define R_EP3(i, b, e) R_EP(i, b, e, 1)
#define R_EP4(i, b, e, s) R_EP(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define R_EPC(...) GET5(__VA_ARGS__, R_EP4, R_EP3, R_EP2, R_EP1)
#define rep(...) R_EPC(__VA_ARGS__)(__VA_ARGS__)
#define trav(x, a) for (auto x : a) 

template<typename T> inline bool umax(T&x, const T& y) { if (x >= y) return false; x = y; return true; }
template<typename T> inline bool umin(T&x, const T& y) { if (x <= y) return false; x = y; return true; }

const int MOD = int(1e9) + 7;

int n, a[100005], k[100005];

namespace Sub2 {
  int dp[5005], pre[5005], end, ans;
  void tst() {
    rep(i, n) {
      pre[i] = i;
      rep(j, i) {
        if (__builtin_popcount(a[i] & a[j]) == k[i]) {
          if (umax(dp[i], dp[j] + 1)) {
            pre[i] = j;
          }
        }
      }
      if (umax(ans, dp[i])) {
        end = i;
      }
    }
    vt<int> path;
    for (int i = 0; i <= ans; end = pre[end], ++i) path.pb(end);
    cout << ans + 1 << "\n";
    reverse(all(path));
    trav(v, path) cout << v + 1 << " ";
    cout << "\n";
  }
};

namespace Sub3 {
  int dp[1 << 8], gd[1 << 8], pre[100005], ans, end;
  void tst() {
    rep(i, n) {
      if (umax(dp[a[i]], 1)) gd[a[i]] = i;
      rep(j, 1 << 8) {
        if (__builtin_popcount(a[i] & j) == k[i]) {
          if (umax(dp[a[i]], dp[j] + 1)) {
            pre[i] = gd[j];
            gd[a[i]] = i;
          }
        }
      }
      if (umax(ans, dp[a[i]])) {
        end = i;
      }
    }
    vt<int> path;
    for (int i = 0; i < ans; end = pre[end], ++i) path.pb(end);
    cout << ans << "\n";
    reverse(all(path));
    trav(v, path) cout << v + 1 << " ";
    cout << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);

  cin >> n;
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> k[i];

  if (n <= 5000) Sub2::tst();
  else if (*max_element(a, a + n) < (1 << 8)) Sub3::tst();

  return 0;
}

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