oj.uz

답안 #306077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306077 2020-09-24T12:48:51 Z myungwoo 버섯 세기 (IOI20_mushrooms) C++17
100 / 100
 9 ms 416 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 7 ms 256 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 7 ms 256 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 9 ms 384 KB Output is correct
16 Correct 9 ms 384 KB Output is correct
17 Correct 4 ms 256 KB Output is correct
18 Correct 6 ms 256 KB Output is correct
19 Correct 7 ms 256 KB Output is correct
20 Correct 7 ms 376 KB Output is correct
21 Correct 7 ms 256 KB Output is correct
22 Correct 9 ms 256 KB Output is correct
23 Correct 7 ms 256 KB Output is correct
24 Correct 5 ms 256 KB Output is correct
25 Correct 8 ms 256 KB Output is correct
26 Correct 7 ms 288 KB Output is correct
27 Correct 8 ms 384 KB Output is correct
28 Correct 7 ms 256 KB Output is correct
29 Correct 8 ms 256 KB Output is correct
30 Correct 7 ms 256 KB Output is correct
31 Correct 7 ms 384 KB Output is correct
32 Correct 7 ms 256 KB Output is correct
33 Correct 9 ms 256 KB Output is correct
34 Correct 9 ms 384 KB Output is correct
35 Correct 9 ms 384 KB Output is correct
36 Correct 7 ms 384 KB Output is correct
37 Correct 7 ms 256 KB Output is correct
38 Correct 9 ms 256 KB Output is correct
39 Correct 8 ms 384 KB Output is correct
40 Correct 7 ms 256 KB Output is correct
41 Correct 8 ms 384 KB Output is correct
42 Correct 8 ms 384 KB Output is correct
43 Correct 7 ms 384 KB Output is correct
44 Correct 7 ms 384 KB Output is correct
45 Correct 7 ms 256 KB Output is correct
46 Correct 7 ms 384 KB Output is correct
47 Correct 7 ms 256 KB Output is correct
48 Correct 9 ms 384 KB Output is correct
49 Correct 7 ms 256 KB Output is correct
50 Correct 8 ms 256 KB Output is correct
51 Correct 8 ms 384 KB Output is correct
52 Correct 7 ms 256 KB Output is correct
53 Correct 7 ms 256 KB Output is correct
54 Correct 7 ms 256 KB Output is correct
55 Correct 8 ms 288 KB Output is correct
56 Correct 8 ms 384 KB Output is correct
57 Correct 7 ms 380 KB Output is correct
58 Correct 7 ms 256 KB Output is correct
59 Correct 8 ms 384 KB Output is correct
60 Correct 6 ms 384 KB Output is correct
61 Correct 7 ms 384 KB Output is correct
62 Correct 1 ms 256 KB Output is correct
63 Correct 0 ms 256 KB Output is correct
64 Correct 0 ms 256 KB Output is correct
65 Correct 1 ms 416 KB Output is correct
66 Correct 0 ms 256 KB Output is correct
67 Correct 1 ms 256 KB Output is correct
68 Correct 0 ms 256 KB Output is correct
69 Correct 1 ms 256 KB Output is correct
70 Correct 1 ms 256 KB Output is correct
71 Correct 1 ms 256 KB Output is correct
72 Correct 1 ms 256 KB Output is correct
73 Correct 1 ms 256 KB Output is correct
74 Correct 1 ms 256 KB Output is correct
75 Correct 1 ms 256 KB Output is correct
76 Correct 0 ms 256 KB Output is correct
77 Correct 1 ms 256 KB Output is correct
78 Correct 1 ms 256 KB Output is correct
79 Correct 1 ms 256 KB Output is correct
80 Correct 1 ms 256 KB Output is correct
81 Correct 1 ms 256 KB Output is correct
82 Correct 0 ms 256 KB Output is correct
83 Correct 1 ms 256 KB Output is correct
84 Correct 1 ms 384 KB Output is correct
85 Correct 1 ms 256 KB Output is correct
86 Correct 1 ms 256 KB Output is correct
87 Correct 1 ms 256 KB Output is correct
88 Correct 1 ms 256 KB Output is correct
89 Correct 1 ms 320 KB Output is correct
90 Correct 1 ms 256 KB Output is correct
91 Correct 0 ms 256 KB Output is correct