Submission #627670

#	Time	Username	Problem	Language	Result	Execution time	Memory
627670		sofapuden	Rarest Insects (IOI22_insects)	C++17	100 / 100	62 ms	416 KiB

insects

#include "insects.h"
#include<bits/stdc++.h>

using namespace std;

int min_cardinality(int n) {
	int am = 1;
	move_inside(0);
	vector<int> st(n,0);
	st[0] = 1;
	int sz = 1;
	for(int i = 1; i < n; ++i){
		move_inside(i);
		if(press_button() != 1)move_outside(i);
		else am++, st[i] = 1, sz++;
	}
	int l = 2, r = n/am, cur = 1;
	int cn = 0;
	while(l <= r){
		cn++;
		int m = (l+r)>>1;
		vector<int> rem;
		if(cn&1){
			for(int i = 0; i < n; ++i){
				if(st[i])continue;
				sz++;
				move_inside(i);
				if(press_button() > m){
					rem.push_back(i);
					sz--;
					move_outside(i);
				}
				if(sz == am*m){
					for(int j = i+1; j < n; ++j){
						if(st[j])continue;
						rem.push_back(j);
					}
					break;
				}
			}
		}
		else{
			for(int i = n-1; ~i; --i){
				if(st[i])continue;
				sz++;
				move_inside(i);
				if(press_button() > m){
					rem.push_back(i);
					sz--;
					move_outside(i);
				}
				if(sz == am*m){
					for(int j = i-1; ~j; --j){
						if(st[j])continue;
						rem.push_back(j);
					}
					break;
				}
			}
		}
		if(sz == am*m){
			for(int i = 0; i < n; ++i)st[i] = 1;
			for(auto x : rem)st[x] = 0;
			cur = m;
			l = m + 1;
		}
		else{
			r = m - 1;
			if(l <= r){
				for(auto x : rem)st[x] = 1;
				for(int i = 0; i < n; ++i){
					if(!st[i]){move_outside(i);sz--;}
				}
			}
		}
	}
	return cur;
}

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