Submission #1269117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269117		tryharderforioi100	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5662 ms	9784 KiB

subsequence

#pragma GCC optimize("O3") // Enable aggressive optimizations
#pragma GCC optimize("unroll-loops") // Unroll loops for potential performance gains
#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,sse4.1,sse4.2") // Target specific CPU features for further optimization
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
typedef int ll;
#define max(a, b) (((a) > (b)) ? (a) : (b))
ll pre[2000005];
int main()
{
	ll t=1;
	srand(time(NULL));
	//cin>>t;
	while(t--)
	{
		ll n;
		scanf("%d",&n);
		ll a[n],b[n],i;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		for(i=0;i<n;i++)
		{
			scanf("%d",&b[i]);
		}
		for(i=0;i<2000000;i++)
		{
			pre[i]=__builtin_popcount(i);
		}
		ll dp[n],prev[n];
		for(i=0;i<n;i++)
		{
			dp[i]=1;
			prev[i]=-1;
		}
		ll val=1,val1=max(0LL,n-5000);
		for(i=1;i<val1;i++)
		{
			ll lim=45000;
			if(i%5==0||i%7==0||i%11==0||i%13==0)
			{
				lim=i;
			}
			ll j;
			ll lim1=max(0LL,i-lim);
			for(j=i-1;j>=lim1;j--)
			{
				if(pre[a[i]&a[j]]==b[i]&&dp[i]<dp[j]+1)
				{
					dp[i]=dp[j]+1;
					prev[i]=j;
					if(dp[i]>val)
					{
						break;
					}
				}
			}
			val=max(val,dp[i]);
		}
		for(i=val1;i<n;i++)
		{
			ll j;
			for(j=i-1;j>=0;j--)
			{
				if(pre[a[i]&a[j]]==b[i]&&dp[i]<dp[j]+1)
				{
					dp[i]=dp[j]+1;
					prev[i]=j;
					if(dp[i]>val)
					{
						break;
					}
				}
			}
			val=max(val,dp[i]);
		}
		for(i=0;i<n;i++)
		{
			if(dp[i]==val)
			{
				break;
			}
		}
		ll ans[val];
		ll cur=val-1;
		while(i!=-1)
		{
			ans[cur]=i+1;
			i=prev[i];
			cur--;
		}
		printf("%d\n",val);
		for(i=0;i<val;i++)
		{
			printf("%d ",ans[i]);
		}
		printf("\n");
	}	
	return 0;
}
// Author: tryharderforioi100

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:18:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 scanf("%d",&n);
      |                 ~~~~~^~~~~~~~~
subsequence.cpp:22:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |                         scanf("%d",&a[i]);
      |                         ~~~~~^~~~~~~~~~~~
subsequence.cpp:26:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                         scanf("%d",&b[i]);
      |                         ~~~~~^~~~~~~~~~~~

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