Submission #833991

#	Time	Username	Problem	Language	Result	Execution time	Memory
833991		penguinman	Counting Mushrooms (IOI20_mushrooms)	C++17	81.00 / 100	8 ms	472 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);
	int now = 1;
	int ans = 1;
	while(now < n){
		if(A.size() >= B.size()){
			vi query;
			int maxi = 0;
			rep(i,0,A.size()){
				if(now == n) break;
				query.pb(now);
				query.pb(A[i]);
				now++;
				ans++;
				maxi++;
			}
			int res = use_machine(query);
			if(res%2) ans--;
			ans -= res/2;
			if(res%2){
				B.pb(query[0]);
			}
			else{
				A.pb(query[0]);
			}
			if(res/2 == 0){
				rep(i,1,query.size()/2) A.pb(query[i*2]);
			}
			if(res/2 == maxi-1){
				rep(i,1,query.size()/2) B.pb(query[i*2]);
			}
		}
		else{
			vi query;
			int maxi = 0;
			rep(i,0,B.size()){
				if(now == n) break;
				query.pb(now);
				query.pb(B[i]);
				now++;
				maxi++;
			}
			int res = use_machine(query);
			if(res%2) ans++;
			ans += res/2;
			if(res%2){
				A.pb(query[0]);
			}
			else{
				B.pb(query[0]);
			}
			if(res/2 == 0){
				rep(i,1,query.size()/2) B.pb(query[i*2]);
			}
			if(res/2 == maxi-1){
				rep(i,1,query.size()/2) A.pb(query[i*2]);
			}
		}
	}
	return ans;
}

• Subtask 1: 81.0036 / 100