Submission #628957

#	Time	Username	Problem	Language	Result	Execution time	Memory
628957		study	Rarest Insects (IOI22_insects)	C++17	53.16 / 100	175 ms	336 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
 
int min_cardinality(int N) {
	vector<int> a(N);
	for (int i=0; i<N; ++i){
		a[i] = i;
	}
	random_shuffle(a.begin(),a.end());
	bitset<2000> inside;
	int nbElems = 0;
	for (int i=0; i<N; ++i){
		move_inside(a[i]);
		if (i != 0){
			int maxFreq = press_button();
			if (maxFreq > 1) move_outside(a[i]);
			else{
				++nbElems;
				inside[a[i]] = true;
//				cout << a[i] << endl;
			}
		}
		else{
			++nbElems;
			inside[a[i]] = true;
//			cout << a[i] << endl;
		}
	}
	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);
			}
/*			for (int i=0; i<crt-mid; ++i){
				inside[last.back()] = false;
				move_outside(last.back());
				last.pop_back();
				in--;
			}
			while (!last.empty()){
				if (press_button() == mid) break;
				int l = last.back();
				move_outside(l);
				inside[l] = false;
				last.pop_back();
				in--;
			}
			if (last.empty()) return ans;
			if (in == nbElems*mid) ok = true;
			crt = mid;*/
		}
		last.clear();
		int delta = mid-crt;
		if (!ok){
			for (int i=0; i<N; ++i){
				if (!inside[a[i]]){
					move_inside(a[i]);
					--delta;
					++in;
					if (delta >= 0){
						inside[a[i]] = true;
						last.emplace_back(a[i]);
						continue;
					}
					crt = press_button();
					if (in == mid*nbElems and crt == mid){
						ok = true;
						inside[a[i]] = true;
//						cout << crt << ' ' << in << endl;
						break;
					}
					if (crt > mid){
						move_outside(a[i]);
						--in;
					}
					else{
//						cout << a[i] << ' ' << in << endl;
						inside[a[i]] = true;
						last.emplace_back(a[i]);
					}
				}
			}
		}
//		cout << mid << endl;
		if (ok){
			crt = mid;
			ans = mid;
			deb = mid+1;
		}
		else fin = mid-1;
	}
	return ans;
/*	for (int iter=0; iter<N; ++iter){
		vector<int> idx;
		for (int i=0; i<N; ++i){
			if (!inside[a[i]]) idx.emplace_back(a[i]);
		}
		if (idx.empty()) return crt;
//		random_shuffle(idx.begin(),idx.end());
		for (int i=0; i<idx.size(); ++i){
			move_inside(idx[i]);
			if (press_button() == crt+1){
				in++;
				inside[idx[i]] = true;
			}
			else move_outside(idx[i]);
			if (in%nbElems == 0) ++crt;
		}
	}
	return crt;*/
}

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