Submission #726339

#	Time	Username	Problem	Language	Result	Execution time	Memory
726339		ismayil	Rarest Insects (IOI22_insects)	C++17	0 / 100	9 ms	336 KiB

insects

#pragma GCC optimize("O3")
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
//g++ -std=c++17 insects.cpp stub.cpp
int D, N;
const int MAX = 2000;
int is_in[MAX];
set<int> in;
bool check(int m){
	vector<int> new_in;
	for(int j = 0; j < N; j++){
		if(is_in[j]) continue;
		move_inside(j);
		if(press_button() > m){
			move_outside(j);
		}else{
			in.insert(j);
			new_in.push_back(j);
		}
	}
	bool flag = false;
	if(in.size() < m * D){
		flag = true;
		while(!new_in.empty()) move_outside(new_in.back()), in.erase(new_in.back());
	}
	
	return flag;
}
int min_cardinality(int n) {
	N = n;
	for(int j = 0; j < N; j++){
		move_inside(j);
		if(press_button() > 1){
			move_outside(j);
		}else{
			in.insert(j);
			is_in[j] = 1;
		}
	}
	D = in.size();

	int l = 1, r = N / D;
	while(l <= r){
		int m = (l + r) / 2;
		if(check(m)) r = m - 1;
		else l = m + 1;
	}
	return r;
}

Compilation message (stderr)

insects.cpp: In function 'bool check(int)':
insects.cpp:23:15: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |  if(in.size() < m * D){
      |     ~~~~~~~~~~^~~~~~~

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