Submission #306077

#	Time	Username	Problem	Language	Result	Execution time	Memory
306077		myungwoo	Counting Mushrooms (IOI20_mushrooms)	C++17	100 / 100	9 ms	416 KiB

mushrooms

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

#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

map <vector<int>, string> rule3_1_2 = {
	{{}, "A0B0C0D1E"},
	{{1}, "0D"},
	{{2}, "0A0D0E"},
	{{3}, "0A1BC0E0D"},
	{{4}, "0A0E0BC1D"},
	{{5}, "0A0BC1E0D"},
	{{6}, "0A0D0E"},
	{{7}, "0D"}
};
map <vector<int>, string> rule1_0_3 = {
	{{}, "0ABCDE"},
	{{1}, "0ABCD"},
	{{1, 1}, "AB0C"},
	{{2}, "A0BCD"},
	{{2, 1}, "AB0CE"},
	{{2, 2}, "ABDC"},
	{{2, 3}, "0C"},
	{{3}, "A0BCE"},
	{{3, 1}, "0B"},
	{{3, 2}, "0BDC"},
	{{3, 3}, "0D"},
	{{3, 4}, "0D"},
	{{4}, "A0BCD"},
	{{4, 2}, "0C"},
	{{4, 3}, "0ABCD"}
};

int eval(const string &choice, int msk, bool base)
{
	int n = choice.length();
	vector <bool> arr(n);
	for (int i=0;i<n;i++){
		if (choice[i] == '0') arr[i] = base;
		else if (choice[i] == '1') arr[i] = base^1;
		else arr[i] = msk>>(choice[i]-'A')&1;
	}
	int ret = 0;
	for (int i=1;i<n;i++) if (arr[i-1] != arr[i]) ret++;
	return ret;
}

int count_mushrooms(int N)
{
	int K = 97;
	vector<int> arr[2] = {{0}, {}};
	int pt = 1;
	// Step 1: Check type of mushroom based on rule
	while (N-pt >= 5 && max(arr[0].size(), arr[1].size()) < K){
		int t = arr[1].size() > arr[0].size();
		auto &rule = (
			arr[t].size() >= 3 && arr[t^1].size() >= 1 ?
				rule3_1_2 :
				rule1_0_3
		);
		vector<int> path;
		vector<bool> valid(32, 1);
		while (rule.count(path)){
			string command = rule[path];
			vector<int> test, p(2);
			for (char c: command){
				if (c == '0' || c == '1') test.push_back(arr[(c-'0')^t][p[(c-'0')^t]++]);
				else test.push_back(pt+(c-'A'));
			}
			int res = use_machine(test);
			for (int i=0;i<32;i++) if (valid[i]){
				if (eval(command, i, t) != res) valid[i] = 0;
			}
			path.push_back(res);
		}
		int cnt = 0, msk;
		for (int i=0;i<32;i++) if (valid[i])
			cnt++, msk = i;
		assert(cnt == 1);
		for (int i=0;i<5;i++)
			arr[msk>>i&1].push_back(pt+i);
		pt += 5;
	}
	// Step 2: Count number of type 0 mushrooms many by one
	int zero_count = arr[0].size();
	while (pt < N){
		int t = arr[1].size() > arr[0].size();
		vector<int> test;
		for (int i=0;i<arr[t].size()&&pt+i<N;i++){
			test.push_back(arr[t][i]);
			test.push_back(pt+i);
		}
		int res = use_machine(test);
		int cnt = res+1>>1;
		if (!t) cnt = test.size()/2-cnt;
		zero_count += cnt;
		arr[res&1^t].push_back(test.back());
		pt += test.size()/2;
	}
	return zero_count;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:55:56: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'int' [-Wsign-compare]
   55 |  while (N-pt >= 5 && max(arr[0].size(), arr[1].size()) < K){
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
mushrooms.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for (int i=0;i<arr[t].size()&&pt+i<N;i++){
      |                ~^~~~~~~~~~~~~~
mushrooms.cpp:95:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |   int cnt = res+1>>1;
      |             ~~~^~
mushrooms.cpp:98:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   98 |   arr[res&1^t].push_back(test.back());
      |       ~~~^~
mushrooms.cpp:82:11: warning: 'msk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |    arr[msk>>i&1].push_back(pt+i);
      |        ~~~^~~

• Subtask 1: 100 / 100