Submission #936532

#	Time	Username	Problem	Language	Result	Execution time	Memory
936532		dshfjka	Martian DNA (BOI18_dna)	C++14	100 / 100	46 ms	7004 KiB

dna

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
	LL n,k,r;
	scanf("%lld %lld %lld",&n,&k,&r);
	LL arr[n+5],brr[n+5];
	memset(brr,0,sizeof(brr));
	for(LL a=1;a<=n;a++)
	{
		scanf("%lld",&arr[a]);
	}
	for(LL a=1;a<=r;a++)
	{
		LL x,y;
		scanf("%lld %lld",&x,&y);
		brr[x]=y;
	}
	LL left=1,right=n;
	LL ans=-1;
	while(left<=right)
	{
		LL mid=(left+right)/2;
	//	printf("mid=%lld\n",mid);
		LL all=0;
		LL jeje[k+5];
		memset(jeje,0,sizeof(jeje));
		for(LL a=1;a<=mid;a++)
		{
			jeje[arr[a]]++;
			if(jeje[arr[a]]==brr[arr[a]])all++;
		//	printf("jeje[%lld]=%lld\n",arr[a],jeje[arr[a]]);
		}
		
		if(all==r)
		{
			ans=mid;
			right=mid-1;
			continue;
		}
		bool sudah=0;
		for(LL a=mid+1;a<=n;a++)
		{
			jeje[arr[a-mid]]--;
			if(jeje[arr[a-mid]]==brr[arr[a-mid]]-1)all--;
			jeje[arr[a]]++;
			if(jeje[arr[a]]==brr[arr[a]])all++;
	//		printf("all = %lld\n",all);
			if(all==r)
			{
				ans=mid;
				right=mid-1;
				sudah=1;
				break;
			}
		}
		if(sudah)continue;
		else {
			left=mid+1;
		}
	}
	if(ans==-1)printf("impossible\n");
	else printf("%lld\n",ans);
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  scanf("%lld %lld %lld",&n,&k,&r);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%lld",&arr[a]);
      |   ~~~~~^~~~~~~~~~~~~~~~
dna.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |   scanf("%lld %lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32