Submission #1189401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189401		hamzabc	Counting Mushrooms (IOI20_mushrooms)	C++20	90.76 / 100	3 ms	460 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>


using namespace std;


int count_mushrooms(int n) {
	vector<int> m(4);
	int c1 = use_machine({ 0, 1 });
	if (n == 2){
		if (c1){
			return 1;
		}
		return 2;
	}
	int c2 = use_machine({ 0, 2 });
	bool inverse = false;
	long long int ret;
	vector<int> Alar, Bler;
	Alar.push_back(0);
	if (c1 == 0)
		Alar.push_back(1);
	else
		Bler.push_back(1);
	if (c2 == 0)
		Alar.push_back(2);
	else
		Bler.push_back(2);
	if (c1 == 0){
		m[0] = 0;
		m[2] = 1;
	}else if (c2 == 0){
		m[0] = 0;
		m[2] = 2;
	}else{
		inverse = true;
		m[0] = 1;
		m[2] = 2;
	}
	for (int i = 0; i < 50 && 4 + i * 2 < n; i++){
		m[1] = 3 + i * 2;
		m[3] = 4 + i * 2;
		c2 = use_machine(m);
		if (c2 & 1){
			if (inverse)
				Alar.push_back(4 + i * 2);
			else
				Bler.push_back(4 + i * 2);
		}else{
			if (inverse)
				Bler.push_back(4 + i * 2);
			else
				Alar.push_back(4 + i * 2);
		}
		if (c2 >= 2){
			if (inverse)
				Alar.push_back(3 + i * 2);
			else
				Bler.push_back(3 + i * 2);
		}else{
			if (inverse)
				Bler.push_back(3 + i * 2);
			else
				Alar.push_back(3 + i * 2);
		}
	}
	int j = max(Alar.size(), Bler.size()) * 2;
	vector<int> amac(j), bmac(j);
	for (int i = 0; i < Alar.size(); i++){
		amac[i * 2] = Alar[i];
	}
	for (int i = 0; i < Bler.size(); i++){
		bmac[i * 2] = Bler[i];
	}
	ret = Alar.size();
	j = Alar.size() + Bler.size();
	int d = 0;
	while (j + amac.size() / 2 < n){
		for (int i = 0; i < amac.size() / 2; i++){
			amac[i * 2 + 1] = j + i;
			bmac[i * 2 + 1] = j + i;
		}
		d = amac.size() / 2;
		if (Alar.size() >= Bler.size()){
			c2 = use_machine(amac);
			ret += amac.size() / 2 - (c2 + 1) / 2;
			if (c2 & 1){
				Bler.push_back(j + amac.size() / 2 - 1);
				if (bmac.size() < Bler.size() * 2){
					bmac.push_back(Bler.back());
					bmac.push_back(0);
					amac.push_back(0);
					amac.push_back(0);
				}else{
					bmac[Bler.size() * 2 - 2] = Bler.back();
				}
			}else{
				Alar.push_back(j + amac.size() / 2 - 1);
				if (amac.size() < Alar.size() * 2){
					amac.push_back(Alar.back());
					amac.push_back(0);
					bmac.push_back(0);
					bmac.push_back(0);
				}else{
					amac[Alar.size() * 2 - 2] = Alar.back();
				}
			}
		}else{
			c2 = use_machine(bmac);
			ret += (c2 + 1) / 2;
			if (c2 & 1){
				Alar.push_back(j + amac.size() / 2 - 1);
				if (amac.size() < Alar.size() * 2){
					amac.push_back(Alar.back());
					amac.push_back(0);
					bmac.push_back(0);
					bmac.push_back(0);
				}else{
					amac[Alar.size() * 2 - 2] = Alar.back();
				}
			}else{
				Bler.push_back(j + amac.size() / 2 - 1);
				if (bmac.size() < Bler.size() * 2){
					bmac.push_back(Bler.back());
					bmac.push_back(0);
					amac.push_back(0);
					amac.push_back(0);
				}else{
					bmac[Bler.size() * 2 - 2] = Bler.back();
				}
			}
		}
		j += d;
	}
	if (n != j){
		vector<int> son((n - j) * 2);
		if (Alar.size() >= son.size() / 2){
			for (int i = 0; i * 2 < son.size(); i++){
				son[i * 2] = Alar[i];
				son[i * 2 + 1] = j + i;
			}
			c2 = use_machine(son);
			ret += son.size() / 2 - (c2 + 1) / 2;
		}else{
			for (int i = 0; i * 2 < son.size(); i++){
				son[i * 2] = Bler[i];
				son[i * 2 + 1] = j + i;
			}
			c2 = use_machine(son);
			ret += (c2 + 1) / 2;
		}
	}
	return ret;
}

• Subtask 1: 90.7631 / 100