Submission #863881

#	Time	Username	Problem	Language	Result	Execution time	Memory
863881		ThylOne	Rarest Insects (IOI22_insects)	C++17	0 / 100	0 ms	344 KiB

insects

#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){
	
	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;
	for(int i=0;i<N;i++){
		mini = min(mini,mem[chef[i]]);
	}
	
	return mini;
}

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