Submission #828994

#	Time	Username	Problem	Language	Result	Execution time	Memory
828994		d4xn	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	0 ms	208 KiB

mushrooms

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

using namespace std;

const int B = 3;

mt19937 rng(9679 + time(nullptr) + chrono::steady_clock::now().time_since_epoch().count() + (uint64_t) new char);

//int cnt;
vector<int> v;

int solve(int l, int r) {
	if (l > r) return 0;
	int sz = r-l+1;
	shuffle(v.begin()+l, v.begin()+r+1, rng);
	
	vector<int> a;
	a.push_back(0);
	for (int i = l; i <= r; i++) {
		a.push_back(v[i]);
	}

	int x = use_machine(a);

	if (!x) return sz;
	else if (x == sz) {
		return sz/2;
	}
	else {
		//int mid = (l+r)/2;
		//int mid = rng() % (r-l) + l; 

		if (x == 1) {
			if (use_machine({a[0], a[1]})) return 0;
			else {
				if (use_machine({a[0], a[2]})) return 1;
				else return 2;
			}
		}
		else {
			if (use_machine({a[0], a[2], a[3]}) == 2) return 3;
			else return 2;
		}

		/*
		int y = solve(l, mid);

		if (y != sz - (x+1)/2) y += solve(mid+1, r);
		return y;
		*/
	}
}

int count_mushrooms(int n) {
	v.resize(n);
	for (int i = 0; i < n; i++) v[i] = i;

	int ans = 1;
	for (int i = 1; i < n; i += B) {
		ans += solve(i, min(n-1, i+B-1));
	}
	return ans;
}

• Subtask 1: 0 / 100