Submission #1269074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269074		tryharderforioi100	Longest beautiful sequence (IZhO17_subsequence)	C11	40 / 100	5879 ms	9928 KiB

subsequence

#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;
		for(i=1;i<n;i++)
		{
			ll lim=rand()%10000+45000;
			ll j;
			for(j=i-1;j>=max(0LL,i-lim);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.c: In function 'main':
subsequence.c:15:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |                 scanf("%d",&n);
      |                 ^~~~~~~~~~~~~~
subsequence.c:19:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |                         scanf("%d",&a[i]);
      |                         ^~~~~~~~~~~~~~~~~
subsequence.c:23:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                         scanf("%d",&b[i]);
      |                         ^~~~~~~~~~~~~~~~~

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