Submission #693802

#	Time	Username	Problem	Language	Result	Execution time	Memory
693802		Pyqe	Rarest Insects (IOI22_insects)	C++17	96.87 / 100	69 ms	328 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"

using namespace std;

long long n;
bitset<2069> ca,spc;

inline void ins(long long x)
{
	ca[x]=1;
	move_inside(x);
}

inline void ers(long long x)
{
	ca[x]=0;
	move_outside(x);
}

inline long long qr()
{
	return press_button();
}

inline long long op(long long x)
{
	long long i,c=0;
	
	for(i=0;i<n;i++)
	{
		if(ca[i]&&!spc[i])
		{
			ers(i);
		}
	}
	for(i=0;i<n;i++)
	{
		if(!spc[i])
		{
			ins(i);
			if(qr()>x)
			{
				ers(i);
			}
		}
		c+=ca[i];
	}
	return c;
}

int min_cardinality(int on)
{
	long long i,k,c,lh,rh,md,zz;
	
	n=on;
	c=op(1);
	if(c==1)
	{
		return n;
	}
	for(zz=1,lh=2,rh=n/c;lh<=rh;)
	{
		md=lh+(rh-lh)*2/3;
		k=op(md);
		if(k==md*c)
		{
			zz=md;
			lh=md+1;
			for(i=0;i<n;i++)
			{
				if(ca[i])
				{
					spc[i]=1;
				}
			}
		}
		else
		{
			rh=md-1;
			for(i=0;i<n;i++)
			{
				if(!ca[i])
				{
					spc[i]=1;
				}
			}
		}
	}
	return zz;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 71.87 / 75