Submission #343055

#	Time	Username	Problem	Language	Result	Execution time	Memory
343055		David_M	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	139 ms	3584 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(){
//	freopen("subsequence.in", "r", stdin);
//	freopen("subsequence.out", "w", stdout);
	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]]){
				c[i]=w[a[i]],d[a[i]]++;
				if(ans<d[a[i]])ans=d[a[i]],e=i;
			}
			d[a[i]]=max(1,d[a[i]]);
			w[a[i]]=i;
			for (j=0; j<256; j++){
				if(a[i]!=j&&bp(a[i]&j)==b[i]&&d[j]>=d[a[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++){if(e==0){if(i<500)cout<<1/0;return 0;}a[i]=e,e=c[e];}
	for (i=ans; i>=1; i--)cout<<a[i]<<" ";
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:37:50: warning: division by zero [-Wdiv-by-zero]
   37 |  for (i=1; i<=ans; i++){if(e==0){if(i<500)cout<<1/0;return 0;}a[i]=e,e=c[e];}
      |                                                 ~^~

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