Submission #202145

#	Time	Username	Problem	Language	Result	Execution time	Memory
202145		mdn2002	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	66 ms	3064 KiB

subsequence

#pragma GCC target ("arch=sandybridge")
 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int n;
int a[101010], k[101010], chain[101010];
 
int bits(int x) {
  return __builtin_popcount(x);
}
 
int par[101010];
pii dp[101010];
 
int main() {
  IO; cin>>n;
  FOR(i,1,n+1) cin>>a[i];
  FOR(i,1,n+1) cin>>k[i];
 
 
  if (n > 5000) {
    int start = 0;
 
    FOR(i,1,n+1) {
      chain[i] = 1;
      // Normally we'd need to check all j < i for maximum dp.
      // Since max value is 2^8-1, we can check all dp values in the range
      // 0..255 due to the fact that the max AND result is 7 bits.
      FOR(j,0,256) {
        if ((bits(a[i] & j) == k[i]) && dp[j].F >= chain[i]) {
          chain[i] = dp[j].F + 1;
          par[i] = dp[j].S;
        }
      }
 
      if (chain[i] >= dp[a[i]].F) {
        dp[a[i]].F = chain[i];
        dp[a[i]].S = i;
      }
      if (chain[i] > chain[start]) start = i;
    }
 
    vector<int> ans;
    for (; start >= 1; ans.pb(start), start = par[start]);
 
    sort(ans.begin(), ans.end());
    cout<<ans.size()<<"\n";
    for (int v : ans)cout<<v<<" ";
    return 0;
  }
  int start = 0;
  FOR(i,1,n+1) {
    chain[i] = 1;
    FOR(j,1,i) {
      bool c = chain[j] >= chain[i];
      if ((bits(a[i] & a[j]) == k[i]) && c) {
        par[i] = j;
        chain[i] = chain[j] + 1;
      }
    }
    if (chain[i] > chain[start]) start = i;
  }
 
  vector<int> ans;
  for (; start >= 1; ans.pb(start), start = par[start]);
 
  sort(ans.begin(), ans.end());
  cout<<ans.size()<<"\n";
  for (int v : ans)cout<<v<<" ";
}

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