제출 #346203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
346203		TheerapakG	Counting Mushrooms (IOI20_mushrooms)	C++17	85.61 / 100	11 ms	512 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> vec[2];

pair<int, int> find_2(int i, bool add=true)
{
	int use = vec[0].size()>vec[1].size()?0:1;
	int ans = use_machine(vector<int>{vec[use][0], i, vec[use][1], i+1});
	if(add)
	{
		if(ans>1) vec[!use].push_back(i);
		else vec[use].push_back(i);
		if(ans%2==0) vec[use].push_back(i+1);
		else vec[!use].push_back(i+1);
	}
	return {use, (ans+1)/2};
}

int count_mushrooms(int n) 
{
	if(n<3) return 2-use_machine({0, 1});
	else
	{
		vec[0].push_back(0);
		int i=1;
		for(;i<3;i++) vec[use_machine({0, i})].push_back(i);
		int s = vec[0].size();
		for(;max(vec[0].size(), vec[1].size())<5&&i+1<n; i+=2)
		{
			auto res = find_2(i);
			s += res.first==0?2-res.second:res.second;
		}
		for(;max(vec[0].size(), vec[1].size())<100&&i+4<n; i+=5)
		{
			int use = vec[0].size()>vec[1].size()?0:1;
			vector<int> query_1;
			for(int j=0; j<5; j++)
			{
				query_1.push_back(vec[use][j]);
				query_1.push_back(i+j);
			}
			int ans_1 = use_machine(query_1);
			if(ans_1%2==0) vec[use].push_back(i+4); // last one is same
			else vec[!use].push_back(i+4); // last one is NOT same
			if(use==0) s+= (10-ans_1)/2;
			else s+= (ans_1+1)/2;
			
			if(ans_1<2) for(int j=0; j<4; j++) vec[use].push_back(i+j);
			else if (ans_1>7) for(int j=0; j<4; j++) vec[!use].push_back(i+j);
			else
			{
				int dif = ans_1/2;
				auto res = find_2(i);

				dif -= res.first==use?res.second:2-res.second;
				if(dif == 0)
				{
					vec[use].push_back(i+2);
					vec[use].push_back(i+3);
				}
				else if(dif == 2)
				{
					vec[!use].push_back(i+2);
					vec[!use].push_back(i+3);
				}
				else find_2(i+2);
			}
		}
		while(i<n)
		{
			int use = vec[0].size()>vec[1].size()?0:1;
			vector<int> query;
			for(auto it=vec[use].begin(); i<n&&it!=vec[use].end(); i++, it++)
			{
				query.push_back(*it);
				query.push_back(i);
			}
			int ans = use_machine(query);
			if(ans%2==0) vec[use].push_back(i-1); // last one is same
			else vec[!use].push_back(i-1); // last one is NOT same
			if(use==0) s+= (query.size()-ans)/2;
			else s+= (ans+1)/2;
		}
		return s;
	}
}

• Subtask 1: 85.6061 / 100