Submission #696825

#	Time	Username	Problem	Language	Result	Execution time	Memory
696825		esomer	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	372 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);

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++;}
		}
		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++;
		}else{
			vector<int> v;
			int asked = 0;
			for(int x : b){
				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--;
		}
	}
	return ans;
}

• Subtask 1: 0 / 100