Submission #629620

#	Time	Username	Problem	Language	Result	Execution time	Memory
629620		study	Rarest Insects (IOI22_insects)	C++17	100 / 100	57 ms	304 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 = fin-(fin-deb)/2;
		if (crt > mid) mid = deb+(fin-deb)/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){
				if (last.empty()) break;
				inside[last.back()] = false;
				move_outside(last.back());
				last.pop_back();
				in--;
			}
			bool yes = false;
			int cnt = 0;
//			random_shuffle(last.begin(),last.end());
			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 (last.empty() and press_button() > mid) return ans;
			if (in == nbElems*mid and yes){
				ok = true;
			}
			crt = mid;
		}
		else last.clear();
		int delta = mid-crt;
		vector<int> outside;
		if (!ok){
//			random_shuffle(a.begin(),a.end());
			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;
						last.emplace_back(a[i]);
//						cout << crt << ' ' << in << endl;
						break;
					}
					if (crt > mid){
						outside.emplace_back(a[i]);
						move_outside(a[i]);
						--in;
						--crt;
					}
					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{
			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:56:9: warning: unused variable 'sqrt_siz' [-Wunused-variable]
   56 |     int sqrt_siz = sqrt((int)last.size());
      |         ^~~~~~~~

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