Submission #830956

#	Time	Username	Problem	Language	Result	Execution time	Memory
830956		pavement	Counting Mushrooms (IOI20_mushrooms)	C++17	10 / 100	178 ms	424 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

vector<bool> solve(int l, int r) {
	if (l == r) {
		return {0};
	}
	int m = (l + r) / 2;
	auto lh = solve(l, m), rh = solve(m + 1, r);
	bool diff = use_machine({m, m + 1}) ^ lh.back() ^ rh[0];
	for (auto i : rh) {
		lh.pb(i ^ diff);
	}
	return lh;
}

int count_mushrooms(int n) {
	auto seq = solve(0, n - 1);
	return count(seq.begin(), seq.end(), 0);
}

• Subtask 1: 10 / 100