제출 #1240155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240155		franuch	버섯 세기 (IOI20_mushrooms)	C++20	25 / 100	34 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 != n % 2 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: 25 / 100