Submission #343010

#	Time	Username	Problem	Language	Result	Execution time	Memory
343010		David_M	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	135 ms	1900 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;
int main(){
	cin>>n;
	for (i=1; i<=n; i++)cin>>a[i],p[i]=1;
	for (i=1; i<=n; i++)cin>>b[i];
	ans=e=1;
	if(n<5001){
		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;
				}
	}else
		for (i=1; i<=n; i++)
			for (j=0; j<256; j++)
				if(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;
				}
	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: 0 / 17
• Subtask 4: 0 / 60