Submission #1241794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241794		nikulid	Rarest Insects (IOI22_insects)	C++20	50.78 / 100	60 ms	424 KiB

insects

#include "insects.h"
#include <vector>

#include <iostream>

using namespace std;

bool debug=1;
#define derr if(debug)cerr

int min_cardinality(int N) {
	// go around to find the value of D
	vector<int> type(N, 0);
	vector<bool> is_in(N,false);
	vector<bool> is_in_l(N, false);
	vector<bool> was_inserted(N, false);
	int D=1;
	move_inside(0);
	type[0]=1;
	is_in[0]=true;
	is_in_l[0]=true;
	for(int i=1; i<N; i++){
		move_inside(i);
		if(press_button() > 1){
			// this is a repeat :p
			move_outside(i);
		} else{
			// this is a new :/
			D++;
			type[i]=D;
			is_in[i]=1;
			is_in_l[i]=1;
		}
	}
	derr<<"$ we have found that D="<<D<<"\n";
	// now we know D ig
	if(D > N/2){
		derr<<"special case (return 1)!!\n";
		return 1;
	}
	else if(D == 1)return N;
	
	int l=1, r=N/2, m=(l+r+1)/2;
	bool incr=1, is_less;
	int I;
	while(r != l){
		derr<<"$ (l,r): ("<<l<<","<<r<<")\n";
		
		// check m
		I=0;
		for(int i=0; i<N; i++){
			if(!incr && was_inserted[i]){
				move_outside(i);
				is_in[i]=0;
			}
			was_inserted[i]=0;
			if(is_in[i]){
				I++;
			}
		}
		if(debug){
			cerr<<"I: "<<I<<", is_in: ";
			for(int i=0; i<N; i++){
				cerr<<is_in[i]<<" ";
			}
			cerr<<"\n";
		}
		for(int i=1; i<N; i++){
			// we currently only have the OGs in
			if(!is_in[i]){
				move_inside(i);
				if(press_button() > m){
					move_outside(i);
				} else{
					I++;
					is_in[i]=1;
					was_inserted[i]=1;
				}
			}
			if(I==D*m){
				break;
			}
		}
		if(I == D*m){
			is_less = 0;
		} else{
			is_less = 1;
		}
		if(is_less){
			r = m-1;
			incr = 0;
		} else{
			for(int i=0; i<N; i++){
				if(is_in[i]){
					is_in_l[i]=1;
				}
			}
			l = m;
			incr = 1;
		}
		m = (l+r+1)/2;
	}
	return l;

}

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