Submission #1069402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069402		GusterGoose27	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	0 ms	344 KiB

mushrooms

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

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

const int inf = 1e9;

int count_mushrooms(int n) {
	if (n < 10) {
		int s = 1;
		for (int i = 0; i < n-1; i++) s += 1-use_machine(vector<int>({0, i+1}));
		return s;
	}
	int bst = inf;
	int num_it = -1;
	for (int i = 0; i < n; i++) { // how many iterations to go through before starting main seq
		int steps = i+2;
		int found = 3+2*i;
		int num_processed = 3+2*i;
		while (found < n) {
			steps++;
			found += (1+num_processed)/2;
			num_processed++;
		}
		if (steps < bst) {
			bst = steps;
			num_it = i;
		}
	}
	vector<int> tp[2];
	tp[0].push_back(0);
	int cutoff = num_it + 2;
	int l = 1;
	for (; l < n && max(sz(tp[0]), sz(tp[1])) < cutoff; ) {
		vector<int> m;
		bool x = sz(tp[1])>sz(tp[0]);
		m.push_back(tp[x][0]);
		m.push_back(l++);
		if (sz(tp[x]) > 1) {
			m.push_back(tp[x][1]);
			m.push_back(l++);
		}
		int v = use_machine(m);
		if (sz(tp[x]) > 1) {
			tp[x^(v&1)].push_back(l-2);
			tp[x^((v/2)&1)].push_back(l-1);
		}
		else tp[x^(v&1)].push_back(l-1);
	}
	int s = 0;
	while (l < n) {
		bool x = sz(tp[1])>sz(tp[0]);
		vector<int> m;
		int num_processed = min(sz(tp[x]), n-l);
		for (int i: tp[x]) {
			m.push_back(i);
			if (l < n) m.push_back(l++);
		}
		int v = use_machine(m);
		int num_bs = (v+(v&1))/2;
		s += x ? num_bs : (num_processed-num_bs);
		if (l < n) {
			tp[(v&1)^x^1].push_back(l-1);
			s -= (v&1)^x;
		}
	}
	return s + sz(tp[0]);
}

• Subtask 1: 0 / 100