Submission #986568

#	Time	Username	Problem	Language	Result	Execution time	Memory
986568		Pyqe	Rarest Insects (IOI22_insects)	C++17	100 / 100	34 ms	608 KiB

insects

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

using namespace std;

long long n,d,c=0,nn,ex[2069];
bitset<2069> ca;

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

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

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

inline long long op(long long x)
{
	long long i;
	
	for(i=1;i<=nn;i++)
	{
		ins(ex[i]);
		if(qr()>x)
		{
			ers(ex[i]);
		}
	}
	return c;
}

int min_cardinality(int on)
{
	long long i,k,sz,md,z=1;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		nn++;
		ex[nn]=i;
	}
	d=op(1);
	nn=0;
	for(i=1;i<=n;i++)
	{
		if(!ca[i])
		{
			nn++;
			ex[nn]=i;
		}
	}
	for(;1;)
	{
		md=min((c+(nn+1)/2-1)/d+1,(c+nn)/d);
		if(md==z)
		{
			break;
		}
		k=op(md);
		if(k==md*d)
		{
			z=md;
			sz=nn;
			nn=0;
			for(i=1;i<=sz;i++)
			{
				if(!ca[ex[i]])
				{
					nn++;
					ex[nn]=ex[i];
				}
			}
		}
		else
		{
			sz=nn;
			nn=0;
			for(i=1;i<=sz;i++)
			{
				if(ca[ex[i]])
				{
					ers(ex[i]);
					nn++;
					ex[nn]=ex[i];
				}
			}
		}
	}
	return z;
}

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