oj.uz

Submission #863881

# Submission time Handle Problem Language Result Execution time Memory
863881 2023-10-21T10:09:40 Z ThylOne Rarest Insects (IOI22_insects) C++17
0 / 100
 0 ms 344 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 344 KB Wrong answer.
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 344 KB Wrong answer.
5 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Wrong answer.
7 Halted 0 ms 0 KB -