Submission #696838

#	Time	Username	Problem	Language	Result	Execution time	Memory
696838		esomer	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	10 ms	464 KiB

mushrooms

#include<bits/stdc++.h>
#include "mushrooms.h"
 
using namespace std;
 
#define endl "\n"
 
typedef long long int ll;

const int MOD = 1e9 + 7;

//~ int use_machine(vector<int> x){
	//~ cout << "Ask: ";
	//~ for(int v : x) cout << v << " "; cout << endl;
	//~ int rep; cin >> rep;
	//~ return rep;
//~ }


int use_machine(vector<int> x);

int count_mushrooms(int n){
	//Initially ask 73 questions.
	vector<int> a = {0};
	vector<int> b;
	int ans = 1;
	int rep = use_machine({0, 1}); 
	if(rep == 1){
		b.push_back(1);
	}else {a.push_back(1); ans++;}
	if(n == 2) return ans;
	rep = use_machine({0, 2}); 
	if(rep == 1){
		b.push_back(2);
	}else {a.push_back(2); ans++;}
	int left = 72;
	int curr = 3;
	while(left > 0 && curr < n){
		if(curr == n - 1){
			rep = use_machine({0, curr});
			if(rep == 0) ans++;
			return ans;
		}
		if((int)a.size() >= 2){
			rep = use_machine({0, curr, a[1], curr + 1});
			if(rep >= 2) b.push_back(curr);
			else {a.push_back(curr); ans++;}
			if(rep % 2 == 1) b.push_back(curr + 1);
			else {a.push_back(curr + 1); ans++;}
		}else{
			rep = use_machine({b[0], curr, b[1], curr + 1});
			if(rep < 2) b.push_back(curr);
			else {a.push_back(curr); ans++;}
			if(rep % 2 == 0) b.push_back(curr + 1);
			else {a.push_back(curr + 1); ans++;}
		}
		curr += 2;
		left--;
	}
	while(curr < n){
		if((int)a.size() < (int)b.size()){
			vector<int> v;
			for(int x : b){
				v.push_back(x);
				v.push_back(curr);
				curr++;
				if(curr == n) break;
			}
			rep = use_machine(v);
			ans += rep / 2;
			if(rep % 2 == 1) {ans++; a.push_back(v.back());}
			else b.push_back(v.back());
		}else{
			vector<int> v;
			int asked = 0;
			for(int x : a){
				v.push_back(x);
				v.push_back(curr);
				curr++;
				asked++;
				if(curr == n) break;  
			}
			rep = use_machine(v);
			ans += asked - rep / 2;
			if(rep % 2 == 1) {ans--; b.push_back(v.back());}
			else a.push_back(v.back());
		}
	}
	return ans;
}

//~ int main(){
	//~ int n; cin >> n;
	//~ cout << count_mushrooms(n) << endl;
//~ }

• Subtask 1: 92.623 / 100