Submission #828990

#	Time	Username	Problem	Language	Result	Execution time	Memory
828990		d4xn	Counting Mushrooms (IOI20_mushrooms)	C++17	10 / 100	185 ms	384 KiB

mushrooms

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

using namespace std;

const int B = 2;

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

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; 
		return solve(l, mid);// + solve(mid+1, r);
	}
}

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;
}

/*
bloques de tamaño x
solve(l, r) -> shuffleo + partir por la mitad o partir random o en sqrt hijos
*/

• Subtask 1: 10 / 100