Submission #430473

#	Time	Username	Problem	Language	Result	Execution time	Memory
430473		amoo_safar	Counting Mushrooms (IOI20_mushrooms)	C++17	91.87 / 100	11 ms	328 KiB

mushrooms

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

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;


int count_mushrooms(int n) {
	if(n == 2)
		return 2 - use_machine({0, 1});

	vector<int> A[2];
	A[0].pb(0);

	int res = use_machine({0, 1});
	int x = 2;

	if(res){
		A[1].pb(1);
		res = use_machine({0, 2});
		x = 3;
		if(res) A[1].pb(2);
		else A[0].pb(2);
	} else A[0].pb(1);
	
	vector<int> rem;
	int lim = 100;
	for(int _ = 0; _ < lim; _ ++){
		if(x + 1 >= n) break;
		int id = 1;
		if(A[0].size() >= A[1].size()) id = 0;
		int r1 = x, r2 = x + 1; x += 2;
		res = use_machine({ r1, A[id][0], r2, A[id][1]});
		A[id ^ (res & 1)].pb(r1);
		A[id ^ (res >>1)].pb(r2);
	}
	vector<int> c(2, 0);

	while(x < n){
		int id = 1;
		if(A[0].size() >= A[1].size()) id = 0;
		int mx = A[id].size();
		int dl = min(mx, n - x);
		vector<int> ASK;
		for(int j = 0; j < dl; j++){
			ASK.pb(x + j);
			ASK.pb(A[id][j]);
		}
		res = use_machine(ASK);
		int mid = dl - 1;
		A[id ^ (res & 1)].pb(x);
		c[id ^ 1] += res / 2;
		c[id] += (mid - (res / 2)); 
		x += dl;
	}
	return c[0] + A[0].size();
}

• Subtask 1: 91.8699 / 100