Submission #640865

#	Time	Username	Problem	Language	Result	Execution time	Memory
640865		jamezzz	Rarest Insects (IOI22_insects)	C++17	47.54 / 100	208 ms	528 KiB

insects

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

bool in[2005];

int min_cardinality(int N){
	int types=0;
	for(int i=0;i<N;++i){
		move_inside(i);
		in[i]=true;
		if(press_button()>1){
			move_outside(i);
			in[i]=false;
		}
		else ++types;
	}
	for(int i=0;i<N;++i){
		if(in[i]){
			move_outside(i);
			in[i]=false;
		}
	}
	int lo=1,hi=N,mid,res;
	vector<int> add;
	int tot=0;
	while(lo<=hi){
		mid=(lo+hi)>>1;
		add.clear();
		for(int i=0;i<N;++i){
			if(in[i])continue;
			move_inside(i);
			in[i]=true;
			++tot;
			if(press_button()>mid){
				move_outside(i);
				in[i]=false;
				--tot;
			}
			else add.push_back(i);
			if(tot==mid*types)break;
		}
		if(tot==mid*types){
			res=mid;
			lo=mid+1;
		}
		else{
			hi=mid-1;
			for(int i:add){
				move_outside(i);
				in[i]=false;
				--tot;
			}
		}
	}
	return res;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:56:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |  return res;
      |         ^~~

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