Submission #388303

#	Time	Username	Problem	Language	Result	Execution time	Memory
388303		JimmyZJX	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	11 ms	348 KiB

mushrooms

#include <cassert>
#include <vector>

using namespace std;

#define forR(i, n) for (int i = 0; i < (n); i++)

int use_machine(vector<int> x);

int use_machine_safe(vector<int> x) {
	int cnt = 0;

	for (int i : x) for (int j : x) {
		if (i == j) cnt++;
	}

	assert(cnt == x.size());

	return use_machine(x);
}

int count_mushrooms(int n) {
	if (n < 400) {
		int cntA = 1;
		for (int i = 1; i < n; i++) {
			if (use_machine(vector<int>{0, i}) == 0)
				cntA++;
		}
		return cntA;
	}

	vector<int> As, Bs; As.push_back(0);

	int i = 1;
	while (As.size() < 2 && Bs.size() < 2) {
		int m = use_machine(vector<int>{0, i});
		if (m == 0) As.push_back(i);
		else Bs.push_back(i);
		i++;
	}

	while (i <= 200) {
		auto as = &As, bs = &Bs;
		if (As.size() < Bs.size()) swap(as, bs);

		if (as->size() >= 4 && bs->size() >= 2) {
			// smart: 5/4 m
			int a1 = (*as)[0], a2 = (*as)[1], a3 = (*as)[2], a4 = (*as)[3];
			int b1 = (*bs)[0], b2 = (*bs)[1];
			int i1 = i, i2 = i + 1, i3 = i + 2, i4 = i + 3, i5 = i + 4;
			int c1, c2, c3, c4, c5;

			int m1 = use_machine(vector<int>{ i1, a1, i2, a2, i3, a3, i4, a4, i5 });

			if (m1 % 2 == 0) {
				// c1 == c5
				int m2 = use_machine(vector<int>{ a1, i1, a2, i5, a3, i2, a4, i3 });
				c1 = c5 = (m2 & 4) > 0;
				c3 = (m2 & 1) > 0;
				c2 = (m2 & 2) > 0;
			} else {
				// c1 != c5
				int m2 = use_machine(vector<int>{ b1, i1, b2, a2, i5, a3, i2, a4, i3 });
				m2--; // b2 - a2
				c5 = (m2 & 4) > 0; c1 = 1 - c5;
				c3 = (m2 & 1) > 0;
				c2 = (m2 & 2) > 0;
			}

			// c4 is unknown
			c4 = (m1 - c1 - c5) / 2 - c2 - c3;

			vector<int> colors{ c1,c2,c3,c4,c5 };
			forR(j, colors.size()) {
				if (colors[j] == 0) {
					as->push_back(i + j);
				} else {
					bs->push_back(i + j);
				}
			}

			i += 5;

		} else {
			// normal: 2m
			int m = use_machine(vector<int>{ (*as)[0], i, (*as)[1], i + 1 });

			if ((m & 2) == 0) {
				as->push_back(i);
			} else {
				bs->push_back(i);
			}

			if ((m & 1) == 0) {
				as->push_back(i + 1);
			} else {
				bs->push_back(i + 1);
			}

			i += 2;
		}
	}

	int cntA = 0;
	while (i < n) {
		int rest = n - i;
		auto as = &As, bs = &Bs;
		if (As.size() < Bs.size()) swap(as, bs); // as is larger

		int l = min(rest, (int)as->size());
		vector<int> test;
		for (int j = 0; j < l; j++) {
			test.push_back((*as)[j]);
			test.push_back(i + j);
		}
		int m = use_machine(test);

		if ((m & 1) == 0) {
			as->push_back(test.back());
		} else {
			bs->push_back(test.back());
		}

		int cnt_b = m / 2;
		int cnt_a = l - 1 - cnt_b;
		if ((*as)[0] == 0) {
			cntA += cnt_a;
		} else {
			cntA += cnt_b;
		}

		i += l;
	}

	return As.size() + cntA;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from mushrooms.cpp:2:
mushrooms.cpp: In function 'int use_machine_safe(std::vector<int>)':
mushrooms.cpp:18:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  assert(cnt == x.size());
      |         ~~~~^~~~~~~~~~~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:7:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define forR(i, n) for (int i = 0; i < (n); i++)
      |                                      ^
mushrooms.cpp:75:4: note: in expansion of macro 'forR'
   75 |    forR(j, colors.size()) {
      |    ^~~~

• Subtask 1: 100 / 100