Submission #1241655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241655		nikulid	Rarest Insects (IOI22_insects)	C++20	25 / 100	98 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;
		}
	}
	
	// now we know D ig
	int sqrtN;
	for(int i=0; i*i < N; i++){
		sqrtN = i;
	}

	if(D > sqrtN){
		// just keep doing sweeps
		derr<<"checking for every answer (repeated sweeps) method...\n";
		int curD = D;
		int answer=1;
		while(true){
			// sweep `answer+1`
			curD=0;
			for(int i=1; i<N; i++){
				if(!is_in[i]){
					move_inside(i);
					if(press_button() > answer+1){
						// this thing occurs many times
						move_outside(i);
					} else{
						is_in[i]=true;
						curD++;
					}
				}
			}
			if(curD < D){
				return answer;
			} else{
				answer++;
			}
		}

	} else{
		// do subtask 1 method
		derr<<"subtask 1 method...\n";
		if(debug){
			cerr<<"is_in: ";
			for(int i=0; i<N; i++){
				cerr<<is_in[i]<<" ";
			}
			cerr<<"\n";
		}
		vector<int> typecount(D+1,0);
		for(int i=0; i<N; i++){
			if(is_in[i]){
				move_outside(i);
			}
		}
		for(int u=0; u<N-1; u++){
			if(!ogtype[u])continue;
			derr<<"u="<<u<<"\n";
			if(debug){                         		
                        	cerr<<"$ types:\n";
                        	for(int i=0; i<N; i++){
                        		cerr<<type[i]<<" ";
                        	}cerr<<"\n";
                        }

			move_inside(u);
			for(int v=u+1; v<N; v++){
				if(type[v] || ogtype[v])continue;
				move_inside(v);
				if(press_button() == 2){
					// same type!
					type[v] = type[u];
				}
				move_outside(v);
			}
			move_outside(u);
		}

		for(int i=0; i<N; i++){
			typecount[type[i]]++;
		}

		int answer=2001;
		for(int i=1; i<D+1; i++){
			answer = min(answer, typecount[i]);
		}

		if(debug){
			cerr<<"$ types:\n";
			for(int i=0; i<N; i++){
				cerr<<type[i]<<" ";
			}cerr<<"\n";
		}

		return answer;
	}
}

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