oj.uz

답안 #303661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
303661 2020-09-20T14:09:07 Z tutis 버섯 세기 (IOI20_mushrooms) C++17
0 / 100
 1 ms 256 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;
	if (n > sz + 5)
	{
		for (int t : {1, 2})
			if (use_machine({0, t}))
				B.push_back(t);
			else
				A.push_back(t);

	}
	else
		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:128:2: warning: "/*" within comment [-Wcomment]
  128 | }/**/
      |

Subtask #1
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 Incorrect 1 ms 256 KB Answer is not correct.
6 Halted 0 ms 0 KB -