Submission #609871

#	Time	Username	Problem	Language	Result	Execution time	Memory
609871		Temmie	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	9 ms	384 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

struct Grid {
	int size;
	int index;
	std::vector <std::bitset <512>> arr;
};

std::vector <Grid> grids(8);

std::vector <int> dac(std::vector <int> input, int depth) {
	if (!depth) {
		return input;
	}
	std::vector <int> interm[2], output[3];
	int acc[2] = { input[(int) input.size() - 2], 0 };
	for (int i = 0; i < (int) input.size() - 2; i += 2) {
		interm[0].push_back((input[i] + input[i + 1] - acc[0]) >> 1);
		interm[1].push_back((input[i + 1] - (input[i] - acc[0])) >> 1);
		output[1].push_back((input[i] + input[i + 1] - acc[0]) & 1);
		acc[1] += output[1].back();
	}
	interm[0].push_back(input[(int) input.size() - 1] - input[(int) input.size() - 2] - acc[1]);
	interm[1].push_back(input[(int) input.size() - 2]);
	output[0] = dac(interm[0], depth - 1);
	output[2] = dac(interm[1], depth - 1);
	output[0].insert(output[0].end(), output[2].begin(), output[2].end());
	output[0].insert(output[0].end(), output[1].begin(), output[1].end());
	return output[0];
}

std::vector <int> dp(210), start(210);

void prep() {
	grids[0].size = 1;
	grids[0].index = 3;
	grids[0].arr.push_back(1);
	for (int i = 1; i <= 7; i++) {
		int shift = grids[i - 1].size;
		grids[i].size = (shift << 1) + (1 << (i - 1)) - 1;
		for (int j = 0; j < (int) grids[i - 1].arr.size() - 1; j++) {
			grids[i].arr.push_back(grids[i - 1].arr[j] | ((grids[i - 1].arr.back() ^ grids[i - 1].arr[j]) << shift));
			grids[i].arr.push_back(grids[i - 1].arr[j] | (grids[i - 1].arr[j] << shift) | (std::bitset <512> (1) << ((shift << 1) + j)));
		}
		grids[i].arr.emplace_back(grids[i - 1].arr.back() << shift);
		grids[i].arr.emplace_back(std::string(grids[i].size, '1'));
		std::vector <int> order;
		for (int j = 0; j < (int) grids[i].arr.size(); j++) {
			order.push_back(grids[i].arr[j].count());
		}
		order[(1 << i) - 1] -= order[(1 << i) - 2];
		std::sort(order.begin(), order.end());
		int count = 0;
		for (int j = 0; j < (int) order.size(); j++) {
			count = std::max(count, ((order[j] << 1) | 1) - j);
		}
		grids[i].index = count;
	}
	std::iota(dp.begin(), dp.begin() + 3, 1);
	for (int i = 2; i < 203; i++) {
		for (int j = 0; j <= 7; j++) {
			if (dp[i] >= grids[j].index && (1 << j) + i <= 203 && dp[i] + grids[j].size > dp[(1 << j) + i]) {
				dp[(1 << j) + i] = dp[i] + grids[j].size + (1 << j);
				start[(1 << j) + i] = j;
			}
		}
	}
}

int count_mushrooms(int n) {
	if (n == 2) {
		return 2 - use_machine({ 0, 1 });
	}
	prep();
	int ans = 1, index = 0;
	for (int i = 2, now = dp[2]; i <= 203 && dp[i] <= n; now = dp[++i]) {
		for (int j = 0; j < 203 - i; j++) {
			now += ((dp[i] + j - 1) >> 1) + 1;
		}
		if (now > ans) {
			ans = now;
			index = i;
		}
	}
	std::vector <int> order;
	for (int i = index; i != 2; i -= 1 << start[i]) {
		order.push_back(start[i]);
	}
	std::reverse(order.begin(), order.end());
	std::vector <int> eo[2];
	int l = 1;
	eo[0].push_back(0);
	for (int i = 0; i < 2; i++) {
		eo[use_machine({ 0, l })].push_back(l++);
	}
	for (int i : order) {
		std::vector <int> idx(1 << i);
		std::iota(idx.begin(), idx.end(), 0);
		std::sort(idx.begin(), idx.end(), [&] (int u, int v) -> bool { return grids[i].arr[u].count() < grids[i].arr[v].count(); });
		std::vector <int> result(1 << i);
		for (int k = 0, cn = 0; k < (1 << i); k++, cn = 0) {
			auto bs = grids[i].arr[idx[k]];
			if (i && idx[k] + 1 == (1 << i)) {
				bs ^= grids[i].arr[idx[k] - 1];
			}
			std::vector <int> q = { l + grids[i].size + k, eo[eo[1].size() > eo[0].size()][cn++] };
			for (int j = 0; j < grids[i].size; j++) {
				if (bs[j]) {
					q.push_back(j + l);
					q.push_back(eo[eo[1].size() > eo[0].size()][cn++]);
				}
			}
			int qr = use_machine(q);
			result[idx[k]] = eo[0].size() >= eo[1].size() ? (qr >> 1) : (cn - 1 - (qr >> 1));
			eo[(eo[0].size() >= eo[1].size()) ^ (~qr & 1)].push_back(l + grids[i].size + k);
		}
		if (i) {
			result[(1 << i) - 1] += result[(1 << i) - 2];
		}
		auto value = dac(result, i);
		for (int j = 0; j < grids[i].size; j++) {
			eo[value[j]].push_back(l + j);
		}
		l += grids[i].size + (1 << i);
	}
	ans = eo[0].size();
	for (int r; l < n; l = r) {
		auto& good = eo[eo[1].size() > eo[0].size()];
		r = std::min(l + (int) good.size(), n);
		std::vector <int> q;
		for (int i = l; i < r; i++) {
			q.push_back(i);
			q.push_back(good[i - l]);
		}
		int qr = use_machine(q);
		if (eo[1].size() > eo[0].size()) {
			qr = ((r - l) << 1) - qr - 1;
		}
		ans += (r - l) - ((qr + 1) >> 1);
		eo[qr & 1].push_back(l);
		l = r;
	}
	return ans;
}

• Subtask 1: 100 / 100