Submission #863882

#	Time	Username	Problem	Language	Result	Execution time	Memory
863882		ThylOne	Rarest Insects (IOI22_insects)	C++17	57.75 / 100	79 ms	1624 KiB

insects

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

using namespace std;
#define pb push_back
vector<int> representant;
vector<int> chef;

void solve(vector<int> inconnus,int inf,int sup){
	#ifdef LOCAL
	cout<<inf<<' '<<sup<<endl;
	for(int v:inconnus){
		cout<<v<<' ';
	}cout<<endl;
	#endif
	if(inf==sup){
		//feuilles
		for(int i:inconnus){
			chef[i] = representant[inf];
		}
		return;
	}else{
		int mid=(inf+sup)/2;
		for(int i=inf;i<=mid;i++)move_inside(representant[i]);
		vector<int> listLeft,listRight;
		for(int Inc:inconnus){
			move_inside(Inc);
			if(press_button()==2){
				listLeft.pb(Inc);
			}else{
				listRight.pb(Inc);
			}
			move_outside(Inc);
		}
		for(int i=inf;i<=mid;i++)move_outside(representant[i]);
		solve(listLeft,inf,mid);
		solve(listRight,mid+1,sup);

	}
}
int min_cardinality(int N) {
	chef.resize(N);
	vector<int> inconnus;
	for(int i=0;i<N;i++){
		move_inside(i);
		if(press_button()>1){
			move_outside(i);
			inconnus.pb(i);
		}else{
			chef[i]=i;
			representant.pb(i);
		}
	}
	for(int i:representant){
		move_outside(i);
	}
	solve(inconnus,0,representant.size()-1);
	map<int,int> mem;
	for(int i=0;i<N;i++){
		mem[chef[i]]++;
	}
	int mini = N+1;
	#ifdef LOCAL
	for(int i=0;i<N;i++){
		cout<<chef[i]<<' ';
	}
	cout<<endl;
	#endif
	for(int i=0;i<N;i++){
		mini = min(mini,mem[chef[i]]);
	}
	
	return mini;
}

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