Submission #956888

#	Time	Username	Problem	Language	Result	Execution time	Memory
956888		n1k	Rarest Insects (IOI22_insects)	C++17	47.51 / 100	124 ms	1432 KiB

insects

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

using namespace std;

int n;

int min_cardinality(int N) {
	n = N;

	vector<int> rest, v, in;

	for(int i=0; i<n; i++){
		move_inside(i);
		v.push_back(i);
		if(press_button()>=2){
			move_outside(i);
			v.pop_back();
			rest.push_back(i);
		}
	}

	int lb = 0, rb = n / v.size();
	while(lb<rb){
		int mb = (lb+rb+1)/2;
		for(int i=0; i<rest.size(); i++){
			move_inside(rest[i]);
			in.push_back(rest[i]);
			if(press_button()>mb+1){
				move_outside(rest[i]);
				in.pop_back();
			}
		}

		if(v.size()*mb==in.size()){
			lb=mb;
		}else{
			rb=mb-1;
		}

		for(auto x:in){
			move_outside(x);
		}
		in.clear();
	}

	return lb+1;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i=0; i<rest.size(); i++){
      |                ~^~~~~~~~~~~~

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