Submission #1240206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240206		franuch	Counting Mushrooms (IOI20_mushrooms)	C++20	92.62 / 100	3 ms	452 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

ll brutforce(ll n) {
	ll ret = 1;
	for (ll i = 1; i + 1 < n; i += 2)
		ret += 2 - use_machine({i, 0, i + 1});
	if (n % 2 == 0)
		ret += use_machine({0, n - 1}) == 0;
	return ret;
}

ll count_mushrooms(ll n) {
	if (n < 400)
		return brutforce(n);
	
	vc<vc<ll>> p = {{0}, {}};
	for (ll i = 1; sz(p[0]) < 2 and sz(p[1]) < 2; i++)
		p[use_machine({0, i})].pub(i);
	
	ll d = 0;
	if (sz(p[0]) < 2)
		d++;
	ll x = p[d][0], y = p[d][1];
	
	
	ll C = 75;
	ll i = sz(p[0]) + sz(p[1]);
	while (sz(p[0]) < C and sz(p[1]) < C) {
		ll q = use_machine({i, x, i + 1, y});
		p[d ^ (q % 2)].pub(i);
		p[d ^ (q / 2)].pub(i + 1);
		i += 2;
	}
	ll ret = sz(p[0]);
	for ( ; i < n; ) {
		if (sz(p[0]) >= sz(p[1])) {
			ll k = sz(p[0]);
			ll r = min(n - 1, i + k - 1);
			vc<ll> q;
			for (ll j = i; j <= r; j++) {
				q.pub(j);
				q.pub(p[0][j - i]);
			}
			x = use_machine(q);
			ret += (r - i + 1) - (x + 1) / 2;
			p[x % 2].pub(i);
			i = r + 1;
		} else {
			ll k = sz(p[1]);
			ll r = min(n - 1, i + k - 1);
			vc<ll> q;
			for (ll j = i; j <= r; j++) {
				q.pub(j);
				q.pub(p[1][j - i]);
			}
			x = use_machine(q);
			ret += (x + 1) / 2;
			p[1 ^ (x % 2)].pub(i);
			i = r + 1;
		}
	}
	return ret;
}

• Subtask 1: 92.623 / 100