Submission #779231

#	Time	Username	Problem	Language	Result	Execution time	Memory
779231		magician	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	58 ms	94668 KiB

subsequence

#include<iostream>
#include<vector>
#include<algorithm>

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

using namespace std;

const int N = (int)1e5 + 1;

int n;
int a[N];
int k[N];

struct State {
  int len, end;
  State(int _len = 0, int _end = 0) {
    len = _len;
    end = _end;
  }
};

State f[MASK(10)][MASK(10)][11];

int bc[MASK(10)][MASK(10)];
int trace[N];

int main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  for(int i = 0; i < MASK(10); i++) {
    for(int j = i; j < MASK(10); j++) {
      bc[i][j] = __builtin_popcount(i & j);
    }
  }

  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) cin >> k[i];

  int p = 1, ans = 1;
  for(int i = 1; i <= n; i++) {
    int l = a[i] >> 10;
    int r = a[i] % MASK(10);
    int lbs = 1;

    trace[i] = i;
    for(int j = 0; j < MASK(10); j++) {
      int needed = k[i] - bc[j][l];
      if(needed < 0 || needed > 10) continue;
      if(f[j][r][needed].len + 1 > lbs) {
        lbs = f[j][r][needed].len + 1;
        trace[i] = f[j][r][needed].end;
      }
    }

    for(int j = 0; j < MASK(10); j++) {
      if(lbs > f[l][j][bc[r][j]].len) {
        f[l][j][bc[r][j]] = State(lbs, i);
      }
    }

    if(lbs > ans) {
      p = i;
      ans = lbs;
    }
  }

  vector<int> seq; seq.clear();
  while(p != trace[p]) {
    seq.push_back(p);
    p = trace[p];
  }
  seq.push_back(p);

  reverse(seq.begin(), seq.end());
  cout << ans << '\n';
  for(int i = 0; i < (int)seq.size(); i++) cout << seq[i] << ' ';
}

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