Submission #635607

#	Time	Username	Problem	Language	Result	Execution time	Memory
635607		l_reho	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	250 ms	592 KiB

insects

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

void move_inside(int i);
void move_outside(int i);
int press_button();

int min_cardinality(int N) {
	int low = 1;
	int high = N;
	int nG = 0;
	
	map<int, bool> isIn;
	for(int i = 0; i < N; i++){
		move_inside(i);
		isIn[i] = true;
		int ret = press_button();
		if(ret == 2){
			isIn[i] = false;
			move_outside(i);
		}else 
			nG++;
	}

	for(int i = 0; i < N; i++) if(isIn[i]) {move_outside(i); isIn[i]=false;}

	while(low <= high){
		int mid = low + (high-low)/2;
		// man mano che arrivo al borderline (mid) mi salvo qualcosa, l'ultimo inserito
		// e conto il numero di borderline
		
		// se il numero di borderline è uguale al numero di gruppi, allora
		// o la risposta è mid, oppure tutti questi superano il borderline
		// altrimenti scendo mid
		int cnt = 0, cnt1 = 0;
		
		for(int i = 0; i < N; i++){
			move_inside(i);
			isIn[i] = true;	
			int ret = press_button();
			if(ret == mid) cnt++;
			if(ret == mid+1){
				isIn[i] = false;
				move_outside(i);
				cnt1++;
			}
		}
		
	
		// cout<<"DEBUG-->"<<mid<<" "<<(N-cnt1)<<" "<<cnt1<<endl;
		
		if(cnt1 + mid * nG == N) low = mid+1;
		else high = mid-1;
		 
		// devo cacciare quelli rimasti
		
		for(int i = 0; i < N; i++) if(isIn[i]) {move_outside(i); isIn[i]=false;}
		
	}

	return low-1;
}

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