Submission #1241760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241760		nikulid	Rarest Insects (IOI22_insects)	C++20	0 / 100	0 ms	408 KiB

insects

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

#include <iostream>

using namespace std;

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

int min_cardinality(int N) {
	// go around to find the value of D
	vector<int> type(N, 0);
	vector<int> ogtype(N,0);
	vector<bool> is_in(N,false);
	int D=1;
	move_inside(0);
	ogtype[0]=1;
	type[0]=1;
	is_in[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++;
			ogtype[i]=D;
			type[i]=D;
			is_in[i]=1;
		}
	}
	derr<<"$ we have found that D="<<D<<"\n";
	// now we know D ig
	if(D > N/2) return 1;
	
	int curD = 1;
	int l=2, r=N, m=(l+r+1)/2;
	bool incr=1, is_less;
	int I;
	while(r != l){
		derr<<"$ (l,r): ("<<l<<","<<r<<")\n";
		// check m
		for(int i=0; i<N; i++){
			if(is_in[i] && !ogtype[i]){
				move_outside(i);
				is_in[i]=0;
			}
		}
		I = D;
		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;
				}
			}
		}
		if(I == D*m){
			is_less = 0;
		} else{
			is_less = 1;
		}
		if(is_less){
			r = m-1;
			incr = 0;
		} else{
			l = m;
			incr = 1;
		}
		m = (l+r+1)/2;
	}
	return l;

}

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