제출 #1240146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240146		franuch	버섯 세기 (IOI20_mushrooms)	C++20	10 / 100	40 ms	576 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> p(n);
	iota(all(p), 0);
	mt19937 rng(2137);
	shuffle(++p.begin(), p.end(), rng);
	const ll K = 3;
	for (ll i = 0; i < n; i += K - 1) {
		ll k = min(K, n - i);
		vc<ll> q(k + 1);
		for (ll l = k; l >= 2; l--) {
			vc<ll> pos;
			for (ll j = i; j < i + l; j++)
				pos.pub(p[j]);
			q[l] = use_machine(pos);
			if (q[l] == 0) {
				for (ll j = i + 1; j < i + l; j++)
					a[p[j]] = a[p[j - 1]];
				break;
			} else if (q[l] == l - 1) {
				for (ll j = i + 1; j < i + l; j++)
					a[p[j]] = a[p[j - 1]] ^ 1;
				break;
			}
		}
		for (ll j = i + 1; j < i + k; j++) {
			if (a[p[j]] == -1)
				a[p[j]] = a[p[j - 1]] ^ (q[j - i + 1] - q[j - i]);
		}
	}
	ll ret = 0;
	for (ll &ai : a)
		if (ai == 0)
			ret++;
	return ret;
}

• Subtask 1: 10 / 100