Submission #1189747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189747		gyg	Counting Mushrooms (IOI20_mushrooms)	C++20	92.62 / 100	3 ms	468 KiB

mushrooms

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

int n;
vec<int> a, b;
int nx;
int a_ex, b_ex;

int qry(vec<int> x) {
	vec<int> y;
	for (int z : x)
		y.push_back(z - 1);
	return use_machine(y);
}

void inc1() {
	int nm = qry({1, nx});
	if (nm == 0) a.push_back(nx);
	else b.push_back(nx);
	nx++;
}

bool on(int x, int i) { return x & (1 << i); }
void inc2() {
	if (a.size() >= 2) {
		int nm = qry({nx, a[0], nx + 1, a[1]});
		if (on(nm, 0)) b.push_back(nx);
		else a.push_back(nx);
		if (on(nm, 1)) b.push_back(nx + 1);
		else a.push_back(nx + 1);
		nx += 2;
	} else {
		int nm = qry({nx, b[0], nx + 1, b[1]});
		if (on(nm, 0)) a.push_back(nx);
		else b.push_back(nx);
		if (on(nm, 1)) a.push_back(nx + 1);
		else b.push_back(nx + 1);
		nx += 2;
	}
}

void inc3() {
	if (a.size() >= b.size()) {
		int sz = min((int) a.size(), n - nx + 1);
		vec<int> qr;
		for (int i = 0; i < 2 * sz; i++) {
			if (i % 2 == 0) qr.push_back(nx + i / 2);
			else qr.push_back(a[i / 2]);
		}
		int nm = qry(qr);
		if (on(nm, 0)) b.push_back(nx);
		else a.push_back(nx);
		b_ex += nm / 2, a_ex += (sz - 1 - nm / 2);
		nx += sz;
	} else {
		int sz = min((int) b.size(), n - nx + 1);
		vec<int> qr;
		for (int i = 0; i < 2 * sz; i++) {
			if (i % 2 == 0) qr.push_back(nx + i / 2);
			else qr.push_back(b[i / 2]);
		}
		int nm = qry(qr);
		if (on(nm, 0)) a.push_back(nx);
		else b.push_back(nx);
		a_ex += nm / 2, b_ex += (sz - 1 - nm / 2);
		nx += sz;
	}
}

int count_mushrooms(int _n) {
	n = _n, a = {1}, b = {}, nx = 2, a_ex = 0, b_ex = 0;

	if (n <= 226) {
		while (nx <= n)
			inc1();		
		return a.size();
	}

	while (max(a.size(), b.size()) <= 1) 
		inc1();
	while (max(a.size(), b.size()) <= 90)
		inc2();
	while (nx <= n)
		inc3();

	return a.size() + a_ex;
}

• Subtask 1: 92.623 / 100