oj.uz

Submission #303663

# Submission time Handle Problem Language Result Execution time Memory
303663 2020-09-20T14:09:59 Z tutis Counting Mushrooms (IOI20_mushrooms) C++17
0 / 100
 2 ms 532 KB 
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
	vector<int>A, B;
	A.push_back(0);
	int sz = 157;
	for (int i = 1; i < sz && i < n; i++)
	{
		if (i + 1 < sz && i + 1 < n && i >= 3)
		{
			if (A.size() >= 2)
			{
				int c = use_machine({A[0], i, A[1], i + 1});
				if (c / 2 == 1)
					B.push_back(i);
				else
					A.push_back(i);
				if (c % 2 == 1)
					B.push_back(i + 1);
				else
					A.push_back(i + 1);
			}
			else
			{
				int c = use_machine({B[0], i, B[1], i + 1});
				if (c / 2 == 1)
					A.push_back(i);
				else
					B.push_back(i);
				if (c % 2 == 1)
					A.push_back(i + 1);
				else
					B.push_back(i + 1);
			}
			i++;
		}
		else {
			if (use_machine({0, i}) == 0)
				A.push_back(i);
			else
				B.push_back(i);
		}
	}
	int ans = A.size();
	vector<int>c;
	for (int i = sz; i < n; i++)
		c.push_back(i);
	int t = 0;
	while (c.size() > 0)
	{
		t++;
		if (t % 2 == 0)
		{
			int cnt = min((int)B.size(), (int)c.size());
			vector<int>m;
			for (int t = 0; t < cnt; t++)
			{
				m.push_back(B[t]);
				m.push_back(c.back());
				c.pop_back();
			}
			int a = use_machine(m);
			ans += (a + 1) / 2;
			if (a % 2 == 0)
				B.push_back(m.back());
			else
				A.push_back(m.back());
		}
		else
		{
			int cnt = min((int)A.size(), (int)c.size());
			vector<int>m;
			for (int t = 0; t < cnt; t++)
			{
				m.push_back(A[t]);
				m.push_back(c.back());
				c.pop_back();
			}
			int a = use_machine(m);
			ans += cnt - (a + 1) / 2;
			if (a % 2 == 0)
				A.push_back(m.back());
			else
				B.push_back(m.back());
		}
	}
	return ans;
}/*
int main()
{
	int n = 20000;
	for (int k = 5; k <= 300; k++)
	{
		int a = 2;
		int b = 1;
		int q = 2;
		int m = 2;
		for (int i = 3; i <= k; i += 2)
		{
			a++;
			b++;
			q++;
			m = i + 2;
		}
		int cnt = n - a - b;
		while (cnt > 0)
		{
			cnt -= max(a, b);
			if (a < b)
				a++;
			else
				b++;
			q++;
		}
		cout << k << " " << q << endl;
	}
}/**/

Compilation message

mushrooms.cpp:118:2: warning: "/*" within comment [-Wcomment]
  118 | }/**/
      |

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 2 ms 532 KB Too small array for query.
8 Halted 0 ms 0 KB -