제출 #343009

#제출 시각아이디문제언어결과실행 시간메모리
343009David_MLongest beautiful sequence (IZhO17_subsequence)C++14
23 / 100
128 ms1900 KiB
#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(){
//	freopen("subsequence.in", "r", stdin);
//	freopen("subsequence.out", "w", stdout);
	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[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]<<" ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...