Submission #433106

#	Time	Username	Problem	Language	Result	Execution time	Memory
433106		peuch	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	154 ms	792 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;

int count_mushrooms(int n) {
	
	vector<int> ans (n);
	vector<int> marc (n);
	marc[0] = 1;
	ans[0] = 1;
	
	vector<int> ask;
	for(int i = 0; i < n; i++)
		ask.push_back(i);
	
	int val = use_machine(ask);
	marc[n - 1] = 1;
	ans[n - 1] = val % 2 == 0;
	
	int a = 0;
	if(val == 0) return n;
	else if(val == 1){
		ask.clear();
		ask.push_back(0);
		ask.push_back(1);
		if(use_machine(ask) == 1) return 1;
		a = 1;
		marc[1] = 1;
		ans[1] = 1;
	}
	else if(val % 2 == 0) a = n - 1;
	else{
		int ini = 1, fim = n - 1;
		while(ini != fim){
			int mid = (ini + fim) >> 1;
			ask.clear();
			ask.push_back(0);
			for(int i = ini; i <= mid; i++)
				ask.push_back(i);
			int aux = use_machine(ask);
			marc[mid] = 1;
			ans[mid] = aux % 2 == 0;
			if(aux % 2 == 0){
				a = mid;
				break;
			}
			if(aux == val) fim = mid - 1;
			else ini = mid + 1, val -= aux;
		}
		if(a == 0) return 1;
	}
	queue<int> fila;
	for(int i = 0; i < n; i++){
		if(marc[i]) continue;
		fila.push(i);
	}
	
	while(fila.size() > 1){
		int c = fila.front();
		fila.pop();
		int d = fila.front();
		fila.pop();
		vector<int> ask2 (4);
		ask2[0] = 0;
		ask2[1] = c;
		ask2[2] = a;
		ask2[3] = d;
		int aux = use_machine(ask2);
		if(aux == 0){
			ans[c] = 1;
			ans[d] = 1;
		}
		else if(aux == 1){
			ans[c] = 1;
			ans[d] = 0;
		}
		else if(aux == 2){
			ans[c] = 0;
			ans[d] = 1;
		}
		else if(aux == 3){
			ans[c] = 0;
			ans[d] = 0;
		}
	}
	if(!fila.empty()){
		int c = fila.front();
		fila.pop();
		vector<int> ask2 (2);
		ask2[0] = 0;
		ask2[1] = c;
		int aux = use_machine(ask2);
		if(aux == 0) ans[c] = 1;
		if(aux == 1) ans[c] = 0;
	}
	
	int ret = 0;
	for(int i = 0; i < n; i++)
		ret += ans[i];
	
	return ret;
}

• Subtask 1: 25 / 100