Submission #388301

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

mushrooms

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>

using namespace std;

typedef long long LL;

#define MAXN 1048579 // 2^20+3

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

#ifdef TEST_LOCAL
int use_machine(vector<int> x) {
	return -1;
}
#else
int use_machine(vector<int> x);
#endif // TEST_LOCAL

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 < 200) {
		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 <= 160) {
		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;
}

#ifdef TEST_LOCAL
vector<vector<int>> gen01Seq(int n) {
	if (n == 1) return vector<vector<int>>{ { 0 }, { 1 }};

	vector<vector<int>> all;
	vector<vector<int>> seqs = gen01Seq(n - 1);
	for (auto s : seqs) {
		s.push_back(0);
		all.push_back(s);
	}
	for (auto s : seqs) {
		s.push_back(1);
		all.push_back(s);
	}

	return all;
}

int calc(vector<int> ns) {
	int ans = 0;
	for (int i = 0; i < ns.size() - 1; i++) {
		if (ns[i] != ns[i + 1])
			ans++;
	}
	return ans;
}

int main() {
	auto s4 = gen01Seq(4);

	vector<vector<int>> alleq2;

	for (auto& s : s4) {
		if (calc(vector<int> { 0, s[0], s[1], s[2], s[3] }) == 2) {
			alleq2.push_back(s);
		}
	}

	int bestStep = 1000000, bestm = -1;
	for (int m = 60; m < 300; m++) {
		int step = m;
		int rest = 20000 - 2 * m;
		int k = m * 2 * 5 / 4;
		// got A*m
		while (rest > 0) {
			rest -= k / 2; step++;
			k++;
		}
		if (step < bestStep) {
			bestStep = step;
			bestm = m;
		}
	}


	return 0;
}
#endif

Compilation message (stderr)

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

• Subtask 1: 98.69 / 100