Submission #1069022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069022		fryingduc	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2820 ms	175404 KiB

subsequence

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

const int maxn = 1e5 + 5;
const int MASK = (1 << 20) + 5;
int n, a[maxn], f[maxn];
int k[maxn];
int b[MASK][21];
int trace_dp[maxn], trace_bit[MASK][21];

void solve() { 
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 1; i <= n; ++i) {
    cin >> k[i];
  }
  int half = 10;
  for(int i = 1; i <= n; ++i) {
    int x = a[i] % (1 << half);
    int y = a[i] >> half;
    
    f[i] = 1;
    for(int submask = 0; submask < (1 << half); ++submask) {
      int cnt = __builtin_popcount(x & submask);
      if(cnt <= k[i]) {
        if(f[i] < b[submask + (y << half)][k[i] - cnt] + 1) {
          f[i] = b[submask + (y << half)][k[i] - cnt] + 1;
          trace_dp[i] = trace_bit[submask + (y << half)][k[i] - cnt];
        }
      }
    }
    
    for(int submask = 0; submask < (1 << half); ++submask) {
      int cnt = __builtin_popcount(submask & y);
        if(b[x + (submask << half)][cnt] < f[i]) {
          b[x + (submask << half)][cnt] = f[i];
          trace_bit[x + (submask << half)][cnt] = i;
        }
    }
  }
  int res = *max_element(f + 1, f + n + 1);
  int pos = 0;
  for(int i = 1; i <= n; ++i) {
    if(f[i] == res) {
      pos = i;
      break;
    }
  }
  cout << res << '\n';
  vector<int> tr;
  while(pos) {
    tr.push_back(pos);
    pos = trace_dp[pos];
  }
  reverse(tr.begin(), tr.end());
  for(auto i:tr) cout << i << " ";
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  solve();
  return 0;
}
/*
4
1 2 3 4
10 0 1 0

5
5 3 5 3 5
10 1 20 1 20
*/

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