Submission #685316

#	Time	Username	Problem	Language	Result	Execution time	Memory
685316		grossly_overconfident	Counting Mushrooms (IOI20_mushrooms)	C++17	53.81 / 100	11 ms	312 KiB

mushrooms

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

vector<int> decipher(int a, int b, int c) {
	vector<int> m = { a, 0, b, c };
	int c1 = use_machine(m);
	if (c1 == 0) {
		m = { 0, 0, 0 };
		return m;
	}
	if (c1 == 3) {
		m = { 1, 1, 0 };
		return m;
	}
	if (c1 == 2) {
		m = { b, a, 0, c };
		c1 = use_machine(m);
		if (c1 == 1) {
			m = { 0, 1, 0 };
		}
		else if (c1 == 3) {
			m = { 1, 0, 1 };
		}
		else if (c1 == 2) {
			m = { 1, 1, 1 };
		}
		return m;
	}
	m = { b, 0, c };
	c1 = use_machine(m);
	if (c1 == 0) {
		m = { 1, 0, 0 };
	}
	else if (c1 == 1) {
		m = { 0, 0, 1 };
	}
	else if (c1 == 2) {
		m = { 0, 1, 1 };
	}
	return m;
}

int count_mushrooms(int n) {
	vector<int> a, b;
	int asize = 1;
	int bsize = 0;
	a.push_back(0);
	if (n < 220) {
		for (int i = 1; i < n; ++i) {
			if (use_machine({ i, 0 }) == 0) {
				a.push_back(i);
				++asize;
			}
		}
		return a.size();
	}
	for (int i = 1; i <= 115; i += 3) { 
		vector<int> take = decipher(i, i + 1, i + 2);
		if (take[0] == 1) {
			b.push_back(i);
			++bsize;
		}
		else {
			a.push_back(i);
			++asize;
		}
		if (take[1] == 1) {
			b.push_back(i + 1);
			++bsize;
		}
		else {
			a.push_back(i + 1);
			++asize;
		}
		if (take[2] == 1) {
			b.push_back(i + 2);
			++bsize;
		}
		else {
			a.push_back(i + 2);
			++asize;
		}
	}// first 115 deciphered

	int count = asize;
	if (asize >= bsize) {
		int i = 118;
		while (i < n) {
			vector<int> pass;
			int psize = 1;
			pass.push_back(a[0]);
			for (int j = 1; j < asize; ++j) {
				pass.push_back(i);
				pass.push_back(a[j]);
				++i;
				psize += 2;
				if (i >= n) {
					break;
				}
			}
			if (psize > 1) {
				count += ((psize - 1) / 2) - (use_machine(pass) / 2);
			}
		}
		return count;
	}
	int i = 118;
	while (i < n) {
		vector<int> pass;
		int psize = 1;
		pass.push_back(b[0]);
		for (int j = 1; j < bsize; ++j) {
			pass.push_back(i);
			pass.push_back(b[j]);
			++i;
			psize += 2;
			if (i >= n) {
				break;
			}
		}
		if (psize > 1) {
			count += use_machine(pass) / 2;
		}
	}
	return count;
}

• Subtask 1: 53.8095 / 100