Submission #629627

#	Time	Username	Problem	Language	Result	Execution time	Memory
629627		study	Rarest Insects (IOI22_insects)	C++17	99.95 / 100	58 ms	332 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){
			int cnt = 0;
			while (!last.empty()){
				int sqrt_siz = sqrt((int)last.size());
				if (cnt%40 == 0 and press_button() <= mid){
					break;
				}
				++cnt;
				int l = last.back();
				move_outside(l);
				inside[l] = false;
				last.pop_back();
				in--;
			}
		}
		else 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;
}

Compilation message (stderr)

insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:34:9: warning: unused variable 'sqrt_siz' [-Wunused-variable]
   34 |     int sqrt_siz = sqrt((int)last.size());
      |         ^~~~~~~~

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