Submission #832993

#	Time	Username	Problem	Language	Result	Execution time	Memory
832993		MeGustaElArroz23	Rarest Insects (IOI22_insects)	C++17	45.45 / 100	175 ms	284 KiB

insects

#include "insects.h"

using namespace std;

#include<bits/stdc++.h>

#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define fi first
#define se second
#define pb push_back
#define vb vector<bool>

int n;
vb box;
vb basic_box;
int basic_box_size;

void create_basic_box(){
	basic_box=vb(n,0);
	for (int i=0;i<n;i++){
		move_inside(i);
		box[i]=1;
		if (press_button()>1){
			move_outside(i);
			box[i]=0;
		}
	}
	basic_box=box;
	basic_box_size=0;
	for (int x:basic_box) basic_box_size+=x;
}

void clear_box(){
	for (int i=0;i<n;i++){
		if (box[i] && (! basic_box[i])){
			box[i]=0;
			move_outside(i);
		}
	}
}

int check_ans(int m){
	for (int i=0;i<n;i++){
		move_inside(i);
		box[i]=1;
		if (press_button()>m){
			move_outside(i);
			box[i]=0;
		}
	}
	int count=0;
	for (int x:box) count+=x;
	if (count==m*basic_box_size){
		basic_box=box;
		return 1;
	}
	else return 0;
}

int min_cardinality(int N) {
	n=N;
	box=vb(n,0);
    create_basic_box();
	clear_box();

	if (basic_box_size==1) return N;

	int l=1;
	int r=n/basic_box_size+1;

	while (l!=r-1){
		//cerr << l << ' ' << r << '\n';
		int m;
		if (r-l>30) m=max((int) (0.38*l+0.62*r),l+1);
		else m=(l+r)/2;
		if (check_ans(m)) l=m;
		else r=m;
		clear_box();
	}

	return l;
}

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