Submission #653233

#	Time	Username	Problem	Language	Result	Execution time	Memory
653233		mychecksedad	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	12 ms	312 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;
	if(n <= 200){
		for(int i = 1; i < n; ++i){
			vector<int> v {0, i};
			ans += 1 - use_machine(v);
		}
		return ans + 1;
	}
	vector<int> a {0}, b; //specific zeros and ones
	int S = 199, 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++]);
				K = j;
			}
			int val = use_machine(v);
			ans += val/2;
		}
		if(K + 1 < n){
			vector<int> v {b[0]};
			int ind = 1;
			for(int j = K + 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++]);
				K = j;
			}
			int val = use_machine(v);
			ans += v.size()/2 - val/2;
		}
		if(K + 1 < n){
			vector<int> v {a[0]};
			int ind = 1;
			for(int j = K + 1; j < n; ++j){
				v.pb(j), v.pb(a[ind++]);
			}
			int val = use_machine(v);
			ans += v.size()/2 - val / 2;
		}
	}


	return ans + a.size();
}

• Subtask 1: 56.7839 / 100