Submission #427509

#	Time	Username	Problem	Language	Result	Execution time	Memory
427509		AugustinasJucas	Counting Mushrooms (IOI20_mushrooms)	C++14	73.86 / 100	16 ms	360 KiB

mushrooms

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

#include "mushrooms.h"

int count_mushrooms(int n) {
	if(n <= 999){
		int A = 1, B = 0;
		for(int i = 1; i < n; i++){
			int kek = use_machine({0, i});
			if(kek == 0){
				A++;
			}else{
				B++;
			}
		}
		return A;
	}
	int ans = 1e9;
	int kekViename = -1;
	for(int i = 1; i < n; i++){
		int st = 2 * i + (n - 2*i) / (i) + 1; // kuo tiksliau, tuo geriau!
		if(ans > st){
			ans = st;
			kekViename = i;
		}
	}
	kekViename -= 40;
	kekViename = max(kekViename, 2);
	int lastTaken = 0;
	vector<int> A = {0}, B;
	int left = n-1;
	int answ = 1;
	//cout << "ieskosiu pirmuju " << kekViename << " * 2 skaiciu!" << endl;
	for(int i = 1; i <= kekViename * 2; i++){
		int kek = use_machine({0, i});
		if(kek == 0){
			A.push_back(i);
			answ++;
		}else{
			B.push_back(i);
		}
		left--;
		lastTaken = i;
		if((int)A.size() >= kekViename+1 || (int)B.size() >= kekViename+1){
			break;
		}
	}
	//cout << "radau! A: "; for(auto x : A) cout << x<< " ";
	//cout << ". B: "; for(auto x : B) cout << x << " "; cout << endl << endl; 
	while(true){
		if(A.size() > B.size()){
			//cout << "I tarpus desim A " << endl;
			// desim A ir i tarpus kitka
			vector<int> st;
			int ind = 1;
			st.push_back(A[0]);
			for(int i = 0; i < min(left, (int) A.size()-1); i++){
				st.push_back(++lastTaken);
				st.push_back(A[ind++]);
			}
			st.pop_back();
			int visoBuvo = min(left, (int) A.size()-1);
			//cout << "gaunam st: "; for(auto x : st) cout << x << " "; cout << endl;  
			left -= min(left, (int) A.size()-1);
			int rz = use_machine(st);
			//cout << "pridedame " << visoBuvo << " - " << rz << "/2\n\n";
			if(rz & 1){
				B.push_back(st.back());
			}else{
				A.push_back(st.back());
			}
			answ += visoBuvo - (rz/2 + (rz & 1));
		}else{
			vector<int> st;
			int ind = 1;
			st.push_back(B[0]);
			for(int i = 0; i < min(left, (int) B.size()-1); i++){
				st.push_back(++lastTaken);
				st.push_back(B[ind++]);
			}
			st.pop_back();
			left -= min(left, (int) B.size()-1);
			int rz = use_machine(st);
			if(rz & 1){
				A.push_back(st.back());
			}else{
				B.push_back(st.back());
			}
			answ += rz/2 + (rz & 1);
		}
		if(left == 0) break;
	}
 	
	return answ;

}

• Subtask 1: 73.8562 / 100