Submission #624657

#	Time	Username	Problem	Language	Result	Execution time	Memory
624657		ollel	Counting Mushrooms (IOI20_mushrooms)	C++14	91.87 / 100	13 ms	472 KiB

mushrooms

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

#include "mushrooms.h"

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<bool> vb;
typedef pair<int,int> pii;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

set<int> A, B;
int n;

int nextQuery = 1;
int ans = 1;

void qa() {
	cerr << "a\n";
	vi Q;
	for (auto a : A) {
		Q.pb(a);
		Q.pb(nextQuery);
		nextQuery++;
		if (nextQuery == n) break;
	}

	int x = use_machine(Q);
	int number_queried = Q.size() / 2;
	int bs = x/2 + (x&1);
	ans += number_queried - bs;
	cerr << number_queried << " " << number_queried - bs << endl;
	if (x & 1) B.insert(Q[Q.size() - 1]);
	else A.insert(Q[Q.size() - 1]);
}

void qb() {
	cerr << "b\n";
	vi Q;
	for (auto a : B) {
		Q.pb(a);
		Q.pb(nextQuery);
		nextQuery++;
		if (nextQuery == n) break;
	}

	int x = use_machine(Q);
	int number_queried = Q.size() / 2;
	int as = x/2 + (x&1);
	ans += as;
	cerr << number_queried << " " << as << endl;

	if (x & 1) A.insert(Q[Q.size() - 1]);
	else B.insert(Q[Q.size() - 1]);
}

void make_query() {
	if (A.size() > B.size()) qa();
	else qb();
}

void make_2_query() {
	if (nextQuery >= n - 1) return;
	vi Q;
	int x1 = nextQuery;
	int x2 = nextQuery+1;
	nextQuery += 2;
	if (A.size() >= 2) {
		auto ai = A.begin();
		int a1 = *ai;
		ai++;
		int a2 = *ai;
		Q = {a1, x1, a2, x2};
	} else {
		auto bi = B.begin();
		int b1 = *bi;
		bi++;
		int b2 = *bi;
		Q = {b1, x1, b2, x2};
	}
	int res = use_machine(Q);
	if (A.size() >= 2) {
		if (res == 0) {
			A.insert(x1);
			A.insert(x2);
			ans+=2;
		} else if (res == 1) {
			A.insert(x1);
			B.insert(x2);
			ans++;
		} else if (res == 2) {
			B.insert(x1);
			A.insert(x2);
			ans++;
		} else {
			B.insert(x1);
			B.insert(x2);
		}
	} else {
		if (res == 0) {
			B.insert(x1);
			B.insert(x2);
		} else if (res == 1) {
			B.insert(x1);
			A.insert(x2);
			ans++;
		} else if (res == 2) {
			A.insert(x1);
			B.insert(x2);
			ans++;
		} else {
			A.insert(x1);
			A.insert(x2);
			ans+=2;

		}
	}
}

void printSets() {
	cout << "A: "; for (auto a:A) cout << a << " "; cout << endl;
	cout << "B: "; for (auto b:B) cout << b << " "; cout << endl << endl;
}

int count_mushrooms(int N) {
	n = N;
	A.insert(0);
	rep(i,0,2) if (nextQuery != n) make_query();
	int MAGIC_NUMBER = 62;
	rep(i,0,MAGIC_NUMBER) {
		int now = (n - (nextQuery)) / max((int)A.size(), (int)B.size());
		int then = (n - nextQuery - max((int)A.size(), (int)B.size())) / (max((int)A.size(), (int)B.size()) + 1);

		if (now < then) break;
		if (nextQuery > n - 2) break;
		make_2_query();
	}

	while (nextQuery != n) make_query();
	return ans;
}

• Subtask 1: 91.8699 / 100