제출 #346083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
346083		TheerapakG	버섯 세기 (IOI20_mushrooms)	C++17	77.66 / 100	12 ms	492 KiB

mushrooms

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

using namespace std;

vector<int> vec[2];

int count_mushrooms(int n) 
{
	if(n<3) return 2-use_machine({0, 1});
	else
	{
		vec[0].push_back(0);
		vec[use_machine({0, 1})].push_back(1);
		vec[use_machine({0, 2})].push_back(2);
		int s = vec[0].size();
		for(int i=3, j=0;i<n;j++)
		{
			int use = vec[0].size()>vec[1].size()?0:1;
			vector<int> query;
			int l = j>80?n:min(n,i+4);
			for(auto it=vec[use].begin(); i<l&&it!=vec[use].end(); i++, it++)
			{
				query.push_back(*it);
				query.push_back(i);
			}
			int ans = use_machine(query);
			if(query.size()==4) 
			{
				if(ans>1) vec[!use].push_back(query[1]);
				else vec[use].push_back(query[1]);
			}
			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: 77.6632 / 100