oj.uz

Submission #654044

# Submission time Handle Problem Language Result Execution time Memory
654044 2022-10-29T16:07:46 Z ellakass Counting Mushrooms (IOI20_mushrooms) C++14
100 / 100
 9 ms 316 KB 
#include <cstdio>
#include "mushrooms.h"

int count_mushrooms(int n)
{
	std::vector < int > V0 = { 0 }, V1;
	int a1 = use_machine({ 0, 1 });
	if (n == 2)
		return 2 - a1;
	int unused = 2, Q = 1;
	if (a1)
	{
		V1.push_back(1);
		int a2 = use_machine({ 0, 2 });
		if (a2)
			V1.push_back(2);
		else
			V0.push_back(2);
		unused++;
		Q++;
	}
	else
		V0.push_back(1);
	while (Q < 82 && std::min(V0.size(), V1.size()) < 3)
	{
		if (unused == n)
			return V0.size();
		if (unused == n - 1)
			return V0.size() + 1 - use_machine({ 0, n - 1 });
		if (V0.size() >= 2)
		{
			int r = use_machine({ V0[0], unused, V0[1], unused + 1 });
			if (r & 2)
				V1.push_back(unused);
			else
				V0.push_back(unused);
			if (r & 1)
				V1.push_back(unused + 1);
			else
				V0.push_back(unused + 1);
			unused += 2;
		}
		else
		{
			int r = use_machine({ V1[0], unused, V1[1], unused + 1 });
			if (r & 2)
				V0.push_back(unused);
			else
				V1.push_back(unused);
			if (r & 1)
				V0.push_back(unused + 1);
			else
				V1.push_back(unused + 1);
			unused += 2;
		}
		Q++;
	}
	int op0 = -1, op1 = -1;
	while (Q < 82)
	{
		if (op0 == -1)
		{
			if (unused == n)
				return V0.size();
			if (unused == n - 1)
				return V0.size() + 1 - use_machine({ 0, n - 1 });
			if (unused == n - 2)
			{
				int r = use_machine({ V0[0], unused, V0[1], unused + 1 });
				return V0.size() + !(r & 2) + !(r & 1);
			}
			int r = use_machine({ V0[0], unused, V0[1], unused + 1, V0[2], unused + 2 });
			if (r & 1)
				V1.push_back(unused + 2);
			else
				V0.push_back(unused + 2);
			r >>= 1;
			if (r == 1)
			{
				op0 = unused;
				op1 = unused + 1;
			}
			else if (r == 0)
			{
				V0.push_back(unused);
				V0.push_back(unused + 1);
			}
			else
			{
				V1.push_back(unused);
				V1.push_back(unused + 1);
			}
			unused += 3;
		}
		else
		{
			if (unused == n)
				return V0.size() + 1;
			if (unused == n - 1)
				return V0.size() + 2 - use_machine({ 0, n - 1 });
			int r = use_machine({ unused, V0[0], unused + 1, V0[1], op0, V0[2], V1[0], op1, V1[1] }) - 1;
			if (r & 1)
				V1.push_back(unused);
			else
				V0.push_back(unused);
			if (r & 2)
				V1.push_back(unused + 1);
			else
				V0.push_back(unused + 1);
			if (r & 4)
			{
				V1.push_back(op0);
				V0.push_back(op1);
			}
			else
			{
				V0.push_back(op0);
				V1.push_back(op1);
			}
			op0 = op1 = -1;
			unused += 2;
		}
		Q++;
	}
	int O = V0.size() + (op0 != -1);
	while (true)
	{
		std::vector < int > query;
		if (V0.size() >= V1.size())
		{
			if (n - unused > V0.size())
			{
				for (int i = 0; i < V0.size(); i++)
				{
					query.push_back(V0[i]);
					query.push_back(unused + i);
				}
				int r = use_machine(query);
				O += V0.size() - (r + 1 >> 1);
				unused += V0.size();
				if (r & 1)
					V1.push_back(unused - 1);
				else
					V0.push_back(unused - 1);
			}
			else
			{
				int L = n - unused;
				for (int i = 0; i < L; i++)
				{
					query.push_back(V0[i]);
					query.push_back(unused + i);
				}
				return O + L - (use_machine(query) + 1 >> 1);
			}
		}
		else
		{
			if (n - unused > V1.size())
			{
				for (int i = 0; i < V1.size(); i++)
				{
					query.push_back(V1[i]);
					query.push_back(unused + i);
				}
				int r = use_machine(query);
				O += r + 1 >> 1;
				unused += V1.size();
				if (r & 1)
					V0.push_back(unused - 1);
				else
					V1.push_back(unused - 1);
			}
			else
			{
				int L = n - unused;
				for (int i = 0; i < L; i++)
				{
					query.push_back(V1[i]);
					query.push_back(unused + i);
				}
				return O + (use_machine(query) + 1 >> 1);
			}
		}
	}
}

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |    if (n - unused > V0.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < V0.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:139:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |     O += V0.size() - (r + 1 >> 1);
      |                       ~~^~~
mushrooms.cpp:154:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |     return O + L - (use_machine(query) + 1 >> 1);
      |                     ~~~~~~~~~~~~~~~~~~~^~~
mushrooms.cpp:159:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |    if (n - unused > V1.size())
      |        ~~~~~~~~~~~^~~~~~~~~~~
mushrooms.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (int i = 0; i < V1.size(); i++)
      |                     ~~^~~~~~~~~~~
mushrooms.cpp:167:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |     O += r + 1 >> 1;
      |          ~~^~~
mushrooms.cpp:182:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |     return O + (use_machine(query) + 1 >> 1);
      |                 ~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 2 ms 292 KB Output is correct
7 Correct 6 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct
9 Correct 6 ms 292 KB Output is correct
10 Correct 5 ms 208 KB Output is correct
11 Correct 5 ms 300 KB Output is correct
12 Correct 6 ms 208 KB Output is correct
13 Correct 6 ms 308 KB Output is correct
14 Correct 4 ms 208 KB Output is correct
15 Correct 7 ms 292 KB Output is correct
16 Correct 6 ms 208 KB Output is correct
17 Correct 3 ms 208 KB Output is correct
18 Correct 5 ms 208 KB Output is correct
19 Correct 7 ms 208 KB Output is correct
20 Correct 5 ms 208 KB Output is correct
21 Correct 7 ms 296 KB Output is correct
22 Correct 9 ms 208 KB Output is correct
23 Correct 4 ms 308 KB Output is correct
24 Correct 4 ms 304 KB Output is correct
25 Correct 6 ms 208 KB Output is correct
26 Correct 6 ms 208 KB Output is correct
27 Correct 5 ms 208 KB Output is correct
28 Correct 5 ms 208 KB Output is correct
29 Correct 6 ms 208 KB Output is correct
30 Correct 6 ms 208 KB Output is correct
31 Correct 6 ms 208 KB Output is correct
32 Correct 6 ms 208 KB Output is correct
33 Correct 6 ms 304 KB Output is correct
34 Correct 6 ms 292 KB Output is correct
35 Correct 8 ms 308 KB Output is correct
36 Correct 5 ms 308 KB Output is correct
37 Correct 7 ms 304 KB Output is correct
38 Correct 7 ms 292 KB Output is correct
39 Correct 7 ms 208 KB Output is correct
40 Correct 7 ms 208 KB Output is correct
41 Correct 6 ms 208 KB Output is correct
42 Correct 7 ms 308 KB Output is correct
43 Correct 6 ms 208 KB Output is correct
44 Correct 7 ms 308 KB Output is correct
45 Correct 6 ms 208 KB Output is correct
46 Correct 5 ms 208 KB Output is correct
47 Correct 7 ms 208 KB Output is correct
48 Correct 6 ms 208 KB Output is correct
49 Correct 6 ms 208 KB Output is correct
50 Correct 7 ms 316 KB Output is correct
51 Correct 6 ms 208 KB Output is correct
52 Correct 7 ms 208 KB Output is correct
53 Correct 6 ms 208 KB Output is correct
54 Correct 7 ms 208 KB Output is correct
55 Correct 5 ms 312 KB Output is correct
56 Correct 6 ms 208 KB Output is correct
57 Correct 6 ms 300 KB Output is correct
58 Correct 9 ms 208 KB Output is correct
59 Correct 6 ms 208 KB Output is correct
60 Correct 6 ms 208 KB Output is correct
61 Correct 6 ms 312 KB Output is correct
62 Correct 0 ms 208 KB Output is correct
63 Correct 0 ms 208 KB Output is correct
64 Correct 0 ms 208 KB Output is correct
65 Correct 1 ms 208 KB Output is correct
66 Correct 0 ms 208 KB Output is correct
67 Correct 1 ms 208 KB Output is correct
68 Correct 1 ms 208 KB Output is correct
69 Correct 1 ms 208 KB Output is correct
70 Correct 0 ms 208 KB Output is correct
71 Correct 0 ms 212 KB Output is correct
72 Correct 0 ms 208 KB Output is correct
73 Correct 0 ms 208 KB Output is correct
74 Correct 0 ms 208 KB Output is correct
75 Correct 1 ms 208 KB Output is correct
76 Correct 0 ms 208 KB Output is correct
77 Correct 1 ms 208 KB Output is correct
78 Correct 0 ms 208 KB Output is correct
79 Correct 0 ms 208 KB Output is correct
80 Correct 0 ms 208 KB Output is correct
81 Correct 1 ms 208 KB Output is correct
82 Correct 0 ms 208 KB Output is correct
83 Correct 1 ms 208 KB Output is correct
84 Correct 0 ms 220 KB Output is correct
85 Correct 1 ms 220 KB Output is correct
86 Correct 0 ms 216 KB Output is correct
87 Correct 0 ms 212 KB Output is correct
88 Correct 1 ms 208 KB Output is correct
89 Correct 1 ms 212 KB Output is correct
90 Correct 1 ms 208 KB Output is correct
91 Correct 1 ms 208 KB Output is correct