Submission #956093

#	Time	Username	Problem	Language	Result	Execution time	Memory
956093		Trisanu_Das	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6095 ms	3500 KiB

subsequence

#include <bits/stdc++.h>
#define bp __builtin_popcount
using namespace std;
const int N=100005;
int i,j,n,a[N],b[N],c[N],w[N],p[N],d[N],ans,e,t;
int main(){
	cin>>n;
	for (i=1; i<=n; i++)cin>>a[i],p[i]=1,t=max(a[i],t);
	for (i=1; i<=n; i++)cin>>b[i];
	ans=e=1;
	if(t<256){
		for (i=1; i<=n; i++){
			if(bp(a[i])==b[i]&&d[a[i]]&&w[a[i]]){
				c[i]=w[a[i]],d[a[i]]++,w[a[i]]=i;
				if(ans<d[a[i]])ans=d[a[i]],e=i;
			}
			d[a[i]]=max(1,d[a[i]]);
			if(!w[a[i]])w[a[i]]=i;
			for (j=0; j<256; j++){
				if(w[j]&&a[i]!=j&&bp(a[i]&j)==b[i]&&d[j]>=d[a[i]]){
					w[a[i]]=i,d[a[i]]=d[j]+1,c[i]=w[j];
					if(ans<d[a[i]])ans=d[a[i]],e=i;
				}
			}
		}
	}else
		for (i=1; i<=n; i++)
			for (j=1; j<i; j++)
				if(bp(a[i]&a[j])==b[i]&&p[j]>=p[i]){
					p[i]=p[j]+1,c[i]=j;
					if(ans<p[i])ans=p[i],e=i;
				}		
			
	cout<<ans<<'\n';
	for (i=1; i<=ans; i++)a[i]=e,e=c[e];
	for (i=ans; i>=1; i--)cout<<a[i]<<" ";
}

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