Submission #830939

#	Time	Username	Problem	Language	Result	Execution time	Memory
830939		caganyanmaz	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	53 ms	452 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
#define pb push_back
using namespace std;

#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int BLOCK = 10;

int n;
set<int> basis;
int _prev;
set<int> unav;


int counter = 0;
bool check(int val)
{
	set<int> l, r;
	for (int i = 0; i < n && (_prev + l.size()) < val * basis.size(); i++)
	{
		if (unav.find(i) != unav.end())
			continue;
		move_inside(i);
		counter++;
		if (press_button() > val)
		{
			counter++;
			move_outside(i);
			r.insert(i);
		}
		else
		{
			l.insert(i);
		}
	}
	bool res = ( _prev + l.size() ) == val * basis.size();
	debug(res, l.size(), _prev, val, basis.size());
	if (res)
	{
		for (int i : l)
			unav.insert(i);
		_prev += l.size();
	}
	else
	{
		for (int i : r)
			unav.insert(i);
		for (int i : l)
		{
			move_outside(i);
			counter++;
		}
	}
	return res;
}

int test_a()
{
	int l = 1, r = 1 + (n / basis.size());
	debug(l, r);
	while (r - l > 1)
	{
		int m = l+r>>1;
		debug(m);
		if (check(m))
			l = m;
		else
			r = m;
	}
	debug(l);
	return l;
}

vector<int> bs;

int min_cardinality(int N)
{
	n = N;
	for (int i = 0; i < n; i++)
	{
		counter++;
		move_inside(i);
		if (press_button() > 1)
		{
			move_outside(i);
			counter++;
		}
		else
		{
			basis.insert(i);
		}
	}	
	for (int i : basis)
	{
		bs.pb(i);
		unav.insert(i);
	}
	_prev = basis.size();
	return test_a();
	
}

Compilation message (stderr)

insects.cpp: In function 'int test_a()':
insects.cpp:68:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   int m = l+r>>1;
      |           ~^~

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