Submission #306248

#	Time	Username	Problem	Language	Result	Execution time	Memory
306248		gs18115	Counting Mushrooms (IOI20_mushrooms)	C++14	100 / 100	10 ms	384 KiB

mushrooms

#include"mushrooms.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
inline int query(initializer_list<int>v)
{
	vector<int>nv;
	for(int t:v)
		nv.eb(t);
	return use_machine(nv);
}
inline void get(int o,int p,vector<int>&av,vector<int>&bv)
{
	int i=av[0],j=av[1];
	int c=query({i,o,j,p});
	(c/2==0?av:bv).eb(o);
	(c%2==0?av:bv).eb(p);
	return;
}
inline void get(int o,int p,int q,int r,int s,vector<int>&av,vector<int>&bv)
{
	int i=av[0],j=av[1],k=av[2];
	int x=bv[0];
	int c=query({o,i,p,j,q,k,r,s});
	int p2=0;
	if(c==0)
		p2=0;
	else if(c==1)
	{
		int c2=query({i,r,j,s});
		if(c2==0)
			p2=1;
		else if(c2==1)
			p2=16;
		else if(c2==3)
			p2=24;
	}
	else if(c==2)
	{
		int c2=query({o,i,s,j,r,k,q});
		if(c2==0)
			p2=2;
		else if(c2==1)
			p2=4;
		else if(c2==2)
			p2=8;
		else if(c2==3)
			p2=17;
		else if(c2==5)
			p2=25;
	}
	else if(c==3)
	{
		int c2=query({q,p,i,s,j,r,o,x});
		if(c2==1)
			p2=9;
		else if(c2==2)
			p2=5;
		else if(c2==3)
			p2=3;
		else if(c2==4)
			p2=20;
		else if(c2==5)
			p2=18;
		else if(c2==6)
			p2=28;
		else if(c2==7)
			p2=26;
	}
	else if(c==4)
	{
		int c2=query({r,i,o,j,s,k,q,p,x});
		if(c2==1)
			p2=6;
		else if(c2==2)
			p2=10;
		else if(c2==4)
			p2=12;
		else if(c2==5)
			p2=19;
		else if(c2==6)
			p2=27;
		else if(c2==7)
			p2=21;
		else if(c2==8)
			p2=29;
	}
	else if(c==5)
	{
		int c2=query({q,i,r,j,s,k,p,o});
		if(c2==2)
			p2=7;
		else if(c2==3)
			p2=11;
		else if(c2==4)
			p2=13;
		else if(c2==5)
			p2=22;
		else if(c2==7)
			p2=30;
	}
	else if(c==6)
	{
		int c2=query({i,r,j,s});
		if(c2==1)
			p2=23;
		else if(c2==2)
			p2=14;
		else if(c2==3)
			p2=31;
	}
	else
		p2=15;
	(p2>>0&1?bv:av).eb(o);
	(p2>>1&1?bv:av).eb(p);
	(p2>>2&1?bv:av).eb(q);
	(p2>>3&1?bv:av).eb(r);
	(p2>>4&1?bv:av).eb(s);
	return;
}
int count_mushrooms(int n)
{
	if(n<440)
	{
		int c=1;
		for(int i=1;i<n;i+=2)
		{
			if(i+1==n)
				c+=1-query({0,i});
			else
				c+=2-query({i,0,i+1});
		}
		return c;
	}
	vector<int>av(1,0),bv;
	{
		int c=query({0,1,2,3});
		if(c==0)
			av.eb(1),av.eb(2),av.eb(3);
		else if(c==1)
		{
			int c2=query({0,3,1,2});
			if(c2==2)
				av.eb(1),av.eb(2),bv.eb(3);
			else if(c2==3)
				av.eb(1),bv.eb(2),bv.eb(3);
			else if(c2==1)
				bv.eb(1),bv.eb(2),bv.eb(3);
		}
		else if(c==2)
		{
			int c2=query({1,0,2,3});
			if(c2==2)
				av.eb(1),bv.eb(2),av.eb(3);
			else if(c2==3)
				bv.eb(1),bv.eb(2),av.eb(3);
			else if(c2==1)
				bv.eb(1),av.eb(2),av.eb(3);
		}
		else
			bv.eb(1),av.eb(2),bv.eb(3);
	}
	if(av.size()>bv.size())
		get(4,5,av,bv);
	else
		get(4,5,bv,av);
	const int size=92;
	for(int i=av.size()+bv.size();(int)av.size()<size&&(int)bv.size()<size;i=av.size()+bv.size())
	{
		if(av.empty())
			get(i,i+1,bv,av);
		else if(bv.empty())
			get(i,i+1,av,bv);
		else if(av.size()>bv.size())
			get(i,i+1,i+2,i+3,i+4,av,bv);
		else
			get(i,i+1,i+2,i+3,i+4,bv,av);
		if((int)max(av.size(),bv.size())*1.2-(int)min(av.size(),bv.size())-0.2>=size)
			break;
	}
	int c=av.size();
	for(int i=av.size()+bv.size();i<n;)
	{
		if(av.size()>bv.size())
		{
			int sz=av.size();
			vector<int>qv;
			for(int j=i;j<i+sz&&j<n;j++)
				qv.eb(j),qv.eb(av[j-i]);
			int c2=use_machine(qv);
			(c2%2==0?av:bv).eb(i);
			c+=(int)qv.size()/2-(c2+1)/2;
			i+=sz;
		}
		else
		{
			int sz=bv.size();
			vector<int>qv;
			for(int j=i;j<i+sz&&j<n;j++)
				qv.eb(j),qv.eb(bv[j-i]);
			int c2=use_machine(qv);
			(c2%2==1?av:bv).eb(i);
			c+=(c2+1)/2;
			i+=sz;
		}
	}
	return c;
}

• Subtask 1: 100 / 100