Submission #799190

#	Time	Username	Problem	Language	Result	Execution time	Memory
799190		EthanKim8683	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6056 ms	92804 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=1e5;
const I A=1<<20;
const I K=20;
const I MAX=1e9;
I a_arr[N];
I k_arr[N];
pair<I,I>pres[A][K/2+1];
I pars[N];
vector<I>ress;
template<class T>void cmb(T&a,T b){a=max(a,b);}
I sup(I x){return x<<(K/2);}
I slw(I x){return x;}
I gup(I x){return x>>(K/2);}
I glw(I x){return x&((1<<(K/2))-1);}
I main(){
  cin.tie(0)->sync_with_stdio(0);
  I n;cin>>n;
  for(I i=0;i<n;i++)cin>>a_arr[i];
  for(I i=0;i<n;i++)cin>>k_arr[i];
  pair<I,I>res={0,MAX};
  for(I i=0;i<n;i++){
    I a=a_arr[i],k=k_arr[i];
    pair<I,I>pre={0,MAX};
    for(I z=0;z<(1<<(K/2));z++){
      I msk=a^sup(z),cnt=__builtin_popcount(gup(a&msk));
      if(k-cnt>=0&&k-cnt<=K/2)cmb(pre,pres[msk][k-cnt]);
    }
    pair<I,I>cur={pre.first+1,i};
    for(I y=0;y<(1<<(K/2));y++){
      I msk=a^slw(y),cnt=__builtin_popcount(glw(a&msk));
      cmb(pres[msk][cnt],cur);
    }
    pars[i]=pre.second,cmb(res,cur);
  }
  auto[len,i]=res;
  for(;i!=MAX;i=pars[i])ress.push_back(i);
  reverse(ress.begin(),ress.end());
  printf("%i\n",len);
  for(auto i:ress)printf("%i ",i+1);
}

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