Submission #629629

#	Time	Username	Problem	Language	Result	Execution time	Memory
629629		study	Rarest Insects (IOI22_insects)	C++17	100 / 100	60 ms	412 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 = fin-(fin-deb)/2;
		if (crt > mid) mid = deb+(fin-deb)/2;
		bool ok = false;
		if (crt > mid){
			for (int i=0; i<crt-mid; ++i){
				if (last.empty()) break;
				inside[last.back()] = false;
				move_outside(last.back());
				last.pop_back();
				in--;
			}
			bool yes = false;
			int cnt = 0;
			while (!last.empty()){
				int sqrt_siz = sqrt((int)last.size());
				if (cnt%40 == 0 and press_button() <= mid){
					yes = true;
					break;
				}
				++cnt;
				int l = last.back();
				move_outside(l);
				inside[l] = false;
				last.pop_back();
				in--;
			}
			if (in == nbElems*mid and yes){
				ok = true;
			}
			crt = mid;
		}
		else last.clear();
		int delta = mid-crt;
		vector<int> outside;
		if (!ok){
			for (int i=0; i<N; ++i){
				if (!inside[i]){
					move_inside(i);
					--delta;
					++in;
					if (delta >= 0){
						inside[i] = true;
						last.emplace_back(i);
						continue;
					}
					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;
						--crt;
					}
					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:43:9: warning: unused variable 'sqrt_siz' [-Wunused-variable]
   43 |     int sqrt_siz = sqrt((int)last.size());
      |         ^~~~~~~~

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