Submission #833586

#	Time	Username	Problem	Language	Result	Execution time	Memory
833586		penguinman	Counting Mushrooms (IOI20_mushrooms)	C++17	56.64 / 100	9 ms	336 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "stub.cpp"
#endif

using ll = int;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(), a.end()

int count_mushrooms(int n) {
	vi A, B;
	A.pb(0);
	constexpr int mate = 90;
	int now = 1;
	while(int(A.size()) < mate && int(B.size()) < mate && now < n){
		int res = use_machine({0,now});
		if(res == 0) A.pb(now);
		else B.pb(now);
		now++;
	}
	int ans = A.size();
	if(A.size() == mate){
		while(now < n){
			vi query;
			rep(i,0,A.size()){
				if(now == n) break;
				query.pb(now);
				query.pb(A[i]);
				now++;
				ans++;
			}
			int res = use_machine(query);
			if(res%2) ans--;
			ans -= res/2;
		}
	}
	else if(B.size() == mate){
		while(now < n){
			vi query;
			rep(i,0,B.size()){
				if(now == n) break;
				query.pb(now);
				query.pb(B[i]);
				now++;
			}
			int res = use_machine(query);
			if(res%2) ans++;
			ans += res/2;
		}
	}
	return ans;
}

• Subtask 1: 56.6416 / 100