oj.uz

Submission #986566

# Submission time Handle Problem Language Result Execution time Memory
986566 2024-05-20T18:54:19 Z Pyqe Rarest Insects (IOI22_insects) C++17
0 / 100
 1 ms 356 KB 
#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=(c+nn/2)/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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 352 KB Wrong answer.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Incorrect 0 ms 356 KB Wrong answer.
3 Halted 0 ms 0 KB -