Submission #1240154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240154		franuch	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	35 ms	420 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 count_mushrooms(ll n) {
	vc<ll> a(n, -1);
	a[0] = 0;
	vc<ll> p0 = {0}, p1 = {};
	for (ll i = 1; i < n; i++) {
		if (use_machine({i - 1, i}) == 0)
			a[i] = a[i - 1];
		else
			a[i] = a[i - 1] ^ 1;
		if (a[i] == 0)
			p0.pub(i);
		else
			p1.pub(i);
		if (i % 2 == 1 and (sz(p0) >= 2 or sz(p1) >= 2))
			break;
	}
	if (sz(p0) + sz(p1) == n)
		return sz(p0);
	ll d, x, y;
	if (sz(p0) >= 2)
		d = 0, x = p0[0], y = p0[1];
	else
		d = 1, x = p1[0], y = p1[1];
	for (ll j = sz(p0) + sz(p1); j < n; j += 2) {
		ll q = use_machine({j, x, j + 1, y});
		a[j] = d ^ (q % 2);
		a[j + 1] = d ^ (q / 2);
	}
	
	for (ll &ai : a)
		cerr << ai << " ";
	cerr << "\n";
	ll ret = 0;
	for (ll &ai : a)
		if (ai == 0)
			ret++;
	return ret;
}

• Subtask 1: 0 / 100