Submission #1295255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295255		Sofiatpc	Counting Mushrooms (IOI20_mushrooms)	C++20	92.62 / 100	5 ms	440 KiB

mushrooms

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

using namespace std;

#define sz(v) (int)v.size()

int count_mushrooms(int n) {
	int tam = 80;

	vector<int> a = {0}, b;
	for (int i = 1; i <= min(n-1,2); i++){
		vector<int> aux = {0,i};
		if(use_machine(aux) == 0)a.push_back(i);
		else b.push_back(i);
	}

	int lst = 2;
	for (int i = 3; i < n; i+=2){
		if(i == n-1){
			vector<int> aux = {0,i};
			if(use_machine(aux) == 0)a.push_back(i);
			else b.push_back(i);
			lst = i;
			break;
		}

		if(sz(a) >= 2){
			vector<int> aux = {i,a[0],i+1,a[1]};
			int x = use_machine(aux);
			if(x == 0){ a.push_back(i); a.push_back(i+1); }
			else if(x == 1){ b.push_back(i); a.push_back(i+1); }
			else if(x == 2){ a.push_back(i); b.push_back(i+1); }
			else { b.push_back(i); b.push_back(i+1); }
		}else{
			vector<int> aux = {i,b[0],i+1,b[1]};
			int x = use_machine(aux);
			if(x == 0){ b.push_back(i); b.push_back(i+1); }
			else if(x == 1){ a.push_back(i); b.push_back(i+1); }
			else if(x == 2){ b.push_back(i); a.push_back(i+1); }
			else { a.push_back(i); a.push_back(i+1); }
		}
		lst = i+1;
		if(sz(a) >= tam || sz(b) >= tam)break;
	}

	if(lst+1 == n)return sz(a);

	vector<int> aux;
	int pt = 0, ans = sz(a);
	for(int i = lst+1; i < n; i++){
		aux.push_back(i);

		if(sz(a) > sz(b))aux.push_back(a[pt]);
		else aux.push_back(b[pt]);
		pt++;

		if(pt == max(sz(a),sz(b)) || i == n-1){
			int x = use_machine(aux);
			if(sz(a) > sz(b))ans += sz(aux) - pt - (x+1)/2;
			else ans += (x+1)/2;

			if(sz(a) > sz(b)){
				if(x%2 == 0)a.push_back(aux[0]);
				else b.push_back(aux[0]);
			}else{
				if(x%2 == 1)a.push_back(aux[0]);
				else b.push_back(aux[0]);
			}

			aux.clear(); pt = 0;
		}
	}
	return ans;
}

• Subtask 1: 92.623 / 100