Submission #1292753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292753		gustavo_d	Counting Mushrooms (IOI20_mushrooms)	C++20	80.14 / 100	4 ms	440 KiB

mushrooms

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

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

const int SQRT = 140;

int count_mushrooms(int n) {
	vector<int> a{0}, b;
	vector<int> query; int pt = 1;
	for (int it=0; it<SQRT and sz(a) + sz(b) < n; it++, pt+=2) {
		query.clear();
		
		if (sz(a) + sz(b) == n-1) {
			query = vector<int> {a[0], pt};
			int res = use_machine(query);
			if (res == 0) a.push_back(pt);
			else b.push_back(pt);
			pt++;
			break;
		}

		if (sz(a) >= 2) {
			query = vector<int> {a[0], pt, a[1], pt+1};
			int res = use_machine(query);
			if (res == 0 or res == 1) a.push_back(pt);
			else b.push_back(pt);
			if (res == 0 or res == 2) a.push_back(pt+1);
			else b.push_back(pt+1); 
			continue;
		}

		query = vector<int>{pt, a[0], pt+1};
		int res = use_machine(query);
		if (res == 0) {
			a.push_back(pt);
			a.push_back(pt+1);
		} else if (res == 2) {
			b.push_back(pt);
			b.push_back(pt+1);
		} else {
			query = vector<int> {pt, a[0]};
			res = use_machine(query);
			if (res == 0) {
				a.push_back(pt);
				b.push_back(pt+1);
			} else {
				b.push_back(pt);
				a.push_back(pt+1);
			}
		}
	}

	int ans = sz(a);
	while (pt < n) {
		bool aBetween = false;
		vector<int> query;
		int qty = 0;
		if (sz(a) >= sz(b)) {
			for (int i=0; i<sz(a)-1 and pt < n; i++, pt++) {
				query.push_back(a[i]);
				query.push_back(pt);
				qty++;
			}
			query.push_back(a.back());
			aBetween = true;
		} else {
			for (int i=0; i<sz(b)-1 and pt < n; i++, pt++) {
				query.push_back(b[i]);
				query.push_back(pt);
				qty++;
			}
			query.push_back(b.back());
			aBetween = false;
		}
		int res = use_machine(query);
		ans += (aBetween ? qty - res / 2 : res / 2);
	}

	return ans;
}

• Subtask 1: 80.1418 / 100