제출 #1167468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167468		Trumling	버섯 세기 (IOI20_mushrooms)	C++20	91.50 / 100	4 ms	460 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()


int count_mushrooms(int n) {
	if(n<=452)
	{
		bool tf=0;
		ll o=use_machine({0,1});
		
		if(n==2)
			return 2 - o;

		int p1=0,p2=1;
		ll count=1;
		if(!o)
			count++;

		ll oo=use_machine({0,2});
		if(!oo)
			count++;
		if(o)
		{
			
			if(o==oo)
			{
				p1=1;
				p2=2;
				tf=1;
			}
			else
				p2=2;
			
		}

		for(int i=3;i<n-1;i+=2)
			{
				ll x=use_machine({p1,i,p2,i+1});
				//cout<<x<<' ';

				if(tf)
					count+= x/2 + x%2;
				else
					count+=2 - (x/2 + x%2);
			}

		if(n%2==0)
			count+= 1 - use_machine({0,n-1});
			
		return count;
	}
	vector<vector<int>>v(2);
	v[0].pb(0);
	ll o=use_machine({0,1});
	v[o].pb(1);
	o=use_machine({0,2});
	v[o].pb(2);
	bool tf=0;

	if(v[1].size()==2)
		tf=1;
	
	for(int i=3;i<=147;i+=2)
	{
		ll x=use_machine({v[tf][0],i,v[tf][1],i+1});
		if(tf)
		{
		v[tf - x/2].pb(i);
		v[tf - x%2].pb(i+1);
		}
		else
		{
		v[x/2].pb(i);
		v[x%2].pb(i+1);
		}
	}
	
	ll sz=v[0].size() + v[1].size();
	ll count=v[0].size();
	ll maxi=sz;
	for(int i=sz;i<n - sz;i+=sz)
	{
		sz=v[0].size() + v[1].size();
		if(i+sz>n)
			break;

		maxi=i+sz;
		vector<int>ans;
		ll idx=0;
		for(int j=0;j<sz;j++)
		{
			if(idx<v[0].size())
				ans.pb(v[0][idx]);
			else
				ans.pb(v[1][idx-v[0].size()]);
			
			ans.pb(i+j);
			idx++;
		}

		ll x=use_machine(ans);
		ll sz0=v[0].size(),sz1=v[1].size();
		ll xx=0;
		ans.clear();
		assert(!ans.size());
		if(v[1].size())
		{
			x-=1;
			for(int j=0;j<v[0].size();j++)
			{
			ans.pb(v[0][j]);	
			ans.pb(i+j);
			}

			xx=use_machine(ans);
			
			count+=sz0 - (xx/2 + xx%2) + (x-(xx-xx%2))/2 + (x-(xx-xx%2))%2;
			

			v[xx%2].pb(i+sz0-1);
			v[1-x%2].pb(i+sz-1);
		}
		else
		{
			count+=sz0 -  (x/2 + x%2);
			v[x%2].pb(i+sz-1);
		}
	}

	if(maxi!=n)
	{

		// for(int i=maxi;i<n-1;i+=2)
		// 	{
		// 		ll x=use_machine({v[tf][0],i,v[tf][1],i+1});
		// 		//cout<<x<<' ';

		// 		if(tf)
		// 			count+= x/2 + x%2;
		// 		else
		// 			count+=2 - (x/2 + x%2);
		// 	}

		// if(n%2==0)
		// 	count+= 1 - use_machine({0,n-1});

		ll idx=0;
		vector<int>ans;

		for(int i=maxi;i<n;i++)
		{
			if(idx<v[0].size())
				ans.pb(v[0][idx]);
			else
				ans.pb(v[1][idx-v[0].size()]);
			
			ans.pb(i);
			idx++;
		}
		ll x=use_machine(ans);
		ll sz0=v[0].size(),sz1=v[1].size();
		ll xx=0;
		
		if(n-maxi>sz0)
		{
			ans.clear();
			assert(!ans.size());

			x-=1;
			for(int j=0;j<v[0].size();j++)
			{
			ans.pb(v[0][j]);	
			ans.pb(maxi+j);
			}

			xx=use_machine(ans);
			
			count+=sz0 - (xx/2 + xx%2) + (x-(xx-xx%2))/2 + (x-(xx-xx%2))%2;

		}
		else
			count+=ans.size()/2 -  (x/2 + x%2);

	}

	return count;
}

• Subtask 1: 91.498 / 100