Submission #621402

#	Time	Username	Problem	Language	Result	Execution time	Memory
621402		beaconmc	Counting Mushrooms (IOI20_mushrooms)	C++14	56.64 / 100	12 ms	344 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef int ll;
using namespace std;
using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


int count_mushrooms(int n) {
	vector<int> as;
	vector<int> bs;
	as.push_back(0);
	FOR(i,1,202){
		if (i>=n) break;
		ll sus = use_machine({0,i});
		if (sus) bs.push_back(i);
		else as.push_back(i);
	}
	if (n <= 202) return as.size();
	ll count = 202;
	ll ans = 0;
	if (as.size() >= 101){
		while (count < n){
			vector<ll> sus;
			sus.push_back(as[0]);
			ll k = min(100, n-count);
			FOR(i,0,k){
				sus.push_back(count+i);
				sus.push_back(as[i+1]);
			}
			ll imp = use_machine(sus);
			ans += k-(imp/2);
			count += k;
		}
	}
	else if (bs.size() >= 101){
		while (count < n){
			vector<ll> sus;
			sus.push_back(bs[0]);
			ll k = min(100, n-count);
			FOR(i,0,k){
				sus.push_back(count+i);
				sus.push_back(bs[i+1]);
			}
			ll imp = use_machine(sus);
			ans += (imp/2);
			count += k;
		}
	}
	return ans + as.size();

}

• Subtask 1: 56.6416 / 100