Submission #629625

#	Time	Username	Problem	Language	Result	Execution time	Memory
629625		study	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	62 ms	408 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
 
int min_cardinality(int N) {
	bitset<2000> inside;
	int nbElems = 0;
	for (int i=0; i<N; ++i){
		move_inside(i);
		if (i != 0){
			int maxFreq = press_button();
			if (maxFreq > 1) move_outside(i);
			else{
				++nbElems;
				inside[i] = true;
			}
		}
		else{
			++nbElems;
			inside[i] = true;
		}
	}
	if (nbElems == 1) return N;
	if (nbElems == N) return 1;
	int in = nbElems, crt = 1;
	int deb = 2, fin = N/nbElems, ans = 1;
	vector<int> last;
	while (deb <= fin){
		int mid = (deb+fin)/2;
		bool ok = false;
		if (crt > mid){
			for (int i:last){
				inside[i] = false;
				in--;
				move_outside(i);
			}
		}
		last.clear();
		vector<int> outside;
		for (int i=0; i<N; ++i){
			if (!inside[i]){
				move_inside(i);
				++in;
				crt = press_button();
				if (in == mid*nbElems and crt == mid){
					ok = true;
					inside[i] = true;
					last.emplace_back(i);
					break;
				}
				if (crt > mid){
					outside.emplace_back(i);
					move_outside(i);
					--in;
				}
				else{
					inside[i] = true;
					last.emplace_back(i);
				}
			}
		}
		if (ok){
			crt = mid;
			ans = mid;
			deb = mid+1;
		}
		else{
			for (int i:outside) inside[i] = true;
			fin = mid-1;
		}
		crt = mid;
	}
	return ans;
}

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