Submission #653224

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

mushrooms

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


int use_machine(std::vector<int> x);
int count_mushrooms(int n) {
	int ans = 0;
	vector<int> a {0}, b; //specific zeros and ones
	int S = sqrt(n), K = 0;
	for(int i = 1; i < min(S + 2, n); i++){
		vector<int> v {0, i};
		int val = use_machine(v);
		if(val==0){
			a.pb(i);
		}else{
			b.pb(i);
		}
		K = i;
	}
	if(a.size() < b.size()){
		S = b.size();
		S--;
		for(int i = K + 1; i + S <= n; i += S){
			vector<int> v {b[0]};
			int ind = 1;
			for(int j = i; j < i + S; ++j){
				v.pb(j), v.pb(b[ind++]);
			}
			int val = use_machine(v);
			ans += val/2;
		}
		if((n-1)%S != 0){
			vector<int> v {b[0]};
			int ind = 1;
			for(int j = (n-1)/S*S+1; j < n; ++j){
				v.pb(j), v.pb(b[ind++]);
			}
			int val = use_machine(v);
			ans += val/2;
		}
	}else{
		S = a.size();
		S--;
		// cout << S <<"S" << K << endl;;
		for(int i = K + 1; i + S <= n; i += S){
			vector<int> v {a[0]};
			int ind = 1;
			for(int j = i; j < i + S; ++j){
				v.pb(j), v.pb(a[ind++]);
			}
			int val = use_machine(v);
			ans += S - val/2;
		}
		if((n-1)%S != 0){
			vector<int> v {a[0]};
			int ind = 1;
			for(int j = (n-1)/S*S+1; j < n; ++j){
				v.pb(j), v.pb(a[ind++]);
			}
			int val = use_machine(v);
			ans += S - val / 2;
		}

	}


	return ans + a.size();
}

• Subtask 1: 0 / 100