Submission #1269068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269068		tryharderforioi100	Longest beautiful sequence (IZhO17_subsequence)	C11	0 / 100	7 ms	8100 KiB

subsequence

#include <stdio.h>
typedef int ll;
#define max(a, b) (((a) > (b)) ? (a) : (b))
ll pre[2000005];
int main()
{
	ll t=1;
	//cin>>t;
	while(t--)
	{
		ll n;
		scanf("%lld",&n);
		ll a[n],b[n],i;
		for(i=0;i<n;i++)
		{
			scanf("%lld",&a[i]);
		}
		for(i=0;i<n;i++)
		{
			scanf("%lld",&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=100000;
			if(b[i]<=10)
			{
				lim=20000;
			}
			ll j;
			for(j=i-1;j>=max(0,i-lim);j--)
			{
				if(pre[a[i]&a[j]]==b[i]&&dp[i]<dp[j]+1)
				{
					dp[i]=dp[j]+1;
					prev[i]=j;
				}
			}
			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("%lld\n",val);
		for(i=0;i<val;i++)
		{
			printf("%lld ",ans[i]);
		}
		printf("\n");
	}	
	return 0;
}
// Author: tryharderforioi100

Compilation message (stderr)

subsequence.c: In function 'main':
subsequence.c:12:27: warning: format '%lld' expects argument of type 'long long int *', but argument 2 has type 'll *' {aka 'int *'} [-Wformat=]
   12 |                 scanf("%lld",&n);
      |                        ~~~^  ~~
      |                           |  |
      |                           |  ll * {aka int *}
      |                           long long int *
      |                        %d
subsequence.c:16:35: warning: format '%lld' expects argument of type 'long long int *', but argument 2 has type 'll *' {aka 'int *'} [-Wformat=]
   16 |                         scanf("%lld",&a[i]);
      |                                ~~~^  ~~~~~
      |                                   |  |
      |                                   |  ll * {aka int *}
      |                                   long long int *
      |                                %d
subsequence.c:20:35: warning: format '%lld' expects argument of type 'long long int *', but argument 2 has type 'll *' {aka 'int *'} [-Wformat=]
   20 |                         scanf("%lld",&b[i]);
      |                                ~~~^  ~~~~~
      |                                   |  |
      |                                   |  ll * {aka int *}
      |                                   long long int *
      |                                %d
subsequence.c:66:28: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'll' {aka 'int'} [-Wformat=]
   66 |                 printf("%lld\n",val);
      |                         ~~~^    ~~~
      |                            |    |
      |                            |    ll {aka int}
      |                            long long int
      |                         %d
subsequence.c:69:36: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'll' {aka 'int'} [-Wformat=]
   69 |                         printf("%lld ",ans[i]);
      |                                 ~~~^   ~~~~~~
      |                                    |      |
      |                                    |      ll {aka int}
      |                                    long long int
      |                                 %d
subsequence.c:12:17: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |                 scanf("%lld",&n);
      |                 ^~~~~~~~~~~~~~~~
subsequence.c:16:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                         scanf("%lld",&a[i]);
      |                         ^~~~~~~~~~~~~~~~~~~
subsequence.c:20:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |                         scanf("%lld",&b[i]);
      |                         ^~~~~~~~~~~~~~~~~~~

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