Submission #1213222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213222		thelegendary08	Counting Mushrooms (IOI20_mushrooms)	C++17	79.86 / 100	4 ms	432 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define vb vector<bool>
using namespace std;
int B = 130;
int count_mushrooms(int n) {
	/*
	std::vector<int> m;
	for (int i = 0; i < n; i++)
		m.push_back(i);
	int c1 = use_machine(m);
	m = {0, 1};
	int c2 = use_machine(m);
	return c1+c2;
	*/
	vi as; vi bs;
	as.pb(0);
	int ret = use_machine({0, 1});
	if(ret == 0){
		as.pb(1);
	}
	else bs.pb(1);
	if(n == 2)return as.size();
	
	ret = use_machine({0,2});
	if(ret == 0){
		as.pb(2);
	}
	else bs.pb(2);
	
	for(int i = 3; i<=B * 2 - 1; i+=2){
		if(i + 1 >= n)break;
		if(as.size() >= 2){
			int ret = use_machine({as[0], i, as[1], i + 1});
			if(ret == 3){
				bs.pb(i);
				bs.pb(i+1);
			}
			else if(ret == 2){
				as.pb(i+1);
				bs.pb(i);
			}
			else if(ret == 1){
				as.pb(i);
				bs.pb(i+1);
			}
			else{
				as.pb(i); as.pb(i+1);
			}
		}
		else{
			int ret = use_machine({bs[0], i, bs[1], i+1});
			if(ret == 3){
				as.pb(i);
				as.pb(i+1);
			}
			else if(ret == 2){
				bs.pb(i+1);
				as.pb(i);
			}
			else if(ret == 1){
				bs.pb(i);
				as.pb(i+1);
			}
			else{
				bs.pb(i); bs.pb(i+1);
			}
		}
	}
	
	
	
	if(n <= B * 2 + 1){
		if(n % 2 == 0){
			int ret = use_machine({0, n-1});
			if(ret == 0)as.pb(n-1);
			else bs.pb(n-1);
		}
		return as.size();
	}
	else{
		int ans = as.size();
		// dout(ans);
		int sz = max(as.size(), bs.size()) - 1;
		for(int i = B * 2 + 1; i < n; i += sz){
			vi thing;
			for(int j = i; j <= min(n-1, i + sz - 1); j++){
				thing.pb(j);
			}
			
			if(as.size() > bs.size()){
				vi quer;
				quer.pb(as[0]);
				int cnt = 1;
				for(auto u : thing){
					quer.pb(u);
					quer.pb(as[cnt]);
					cnt++;
				}
				int ret = use_machine(quer);
				ans += thing.size() - (ret / 2);
			}
			else{
				vi quer;
				quer.pb(bs[0]);
				int cnt = 1;
				for(auto u : thing){
					quer.pb(u);
					quer.pb(bs[cnt]);
					cnt++;
				}
				int ret = use_machine(quer);
				ans += ret / 2;
			}
			
			
		}
		return ans;
	}
	return 0;
}

• Subtask 1: 79.8587 / 100