Submission #303604

#	Time	Username	Problem	Language	Result	Execution time	Memory
303604		Gajowy	Counting Mushrooms (IOI20_mushrooms)	C++14	92.24 / 100	13 ms	512 KiB

mushrooms

#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include "mushrooms.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
float pi=3.14159265358979323846;

int prep=90;

int count_mushrooms(int n)
{
	vector<int> unknown,red={0},blue,qvec;
	for(int i=1;i<n;i++)
		unknown.eb(i);
	mt19937 rng(time);
	uniform_int_distribution<int> rng2(0,1);
	shuffle(all(unknown),rng);
	int res=1;
	while(size(unknown)>1&&prep>0)
	{
		prep--;
		qvec.clear();
		if(max(size(red),size(blue))==1)
		{
			qvec.eb(red[0]);
			qvec.eb(unknown.back()),unknown.pop_back();
			int ans=use_machine(qvec);
			if(ans==1)
				blue.eb(qvec.back());
			else
				red.eb(qvec.back()),res++;
		}
		else
		if(min(size(red),size(blue))<2)
		{
			if(size(red)>1)
			{
				qvec.eb(red[0]);
				qvec.eb(unknown.back()),unknown.pop_back();
				qvec.eb(red[1]);
				qvec.eb(unknown.back()),unknown.pop_back();
				int ans=use_machine(qvec);
				if(ans==0)
					res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
				else
				if(ans==1)
					res+=1,red.eb(qvec[1]),blue.eb(qvec[3]);
				else
				if(ans==2)
					res+=1,red.eb(qvec[3]),blue.eb(qvec[1]);
				else
				if(ans==3)
					blue.eb(qvec[1]),blue.eb(qvec[3]);	
			}
			else
			{
				qvec.eb(blue[0]);
				qvec.eb(unknown.back()),unknown.pop_back();
				qvec.eb(blue[1]);
				qvec.eb(unknown.back()),unknown.pop_back();
				int ans=use_machine(qvec);
				if(ans==0)
					blue.eb(qvec[1]),blue.eb(qvec[3]);
				else
				if(ans==1)
					res+=1,blue.eb(qvec[1]),red.eb(qvec[3]);
				else
				if(ans==2)
					res+=1,blue.eb(qvec[3]),red.eb(qvec[1]);
				else
				if(ans==3)
					res+=2,red.eb(qvec[1]),red.eb(qvec[3]);	
			}
		}
		else
		{
			if(rng2(rng)!=2137)
			{
				qvec.eb(red[0]);
				qvec.eb(unknown.back()),unknown.pop_back();
				qvec.eb(red[1]);
				qvec.eb(unknown.back()),unknown.pop_back();
				int ans=use_machine(qvec);
				if(ans==0)
					res+=2,red.eb(qvec[1]),red.eb(qvec[3]);
				else
				if(ans==1)
					res+=1,red.eb(qvec[1]),blue.eb(qvec[3]);
				else
				if(ans==2)
					res+=1,red.eb(qvec[3]),blue.eb(qvec[1]);
				else
				if(ans==3)
					blue.eb(qvec[1]),blue.eb(qvec[3]);	
			}
			else
			{
				qvec.eb(blue[0]);
				qvec.eb(unknown.back()),unknown.pop_back();
				qvec.eb(blue[1]);
				qvec.eb(unknown.back()),unknown.pop_back();
				int ans=use_machine(qvec);
				if(ans==0)
					blue.eb(qvec[1]),blue.eb(qvec[3]);
				else
				if(ans==1)
					res+=1,blue.eb(qvec[1]),red.eb(qvec[3]);
				else
				if(ans==2)
					res+=1,blue.eb(qvec[3]),red.eb(qvec[1]);
				else
				if(ans==3)
					res+=2,red.eb(qvec[1]),red.eb(qvec[3]);	
			}
		}
	}
	while(size(unknown))
	{
		qvec.clear();
		if(size(red)>size(blue))
		{
			int p=0;
			while(p<size(red)&&size(unknown)>0)
				qvec.eb(red[p++]),qvec.eb(unknown.back()),unknown.pop_back();
			int ans=use_machine(qvec);
			if(ans&1)
				blue.eb(qvec.back()),ans++;
			else
				red.eb(qvec.back());
			ans/=2;
			res+=p-ans;
		}
		else
		{
			int p=0;
			while(p<size(blue)&&size(unknown)>0)
				qvec.eb(blue[p++]),qvec.eb(unknown.back()),unknown.pop_back();
			int ans=use_machine(qvec);
			if(ans&1)
				red.eb(qvec.back()),ans++;
			else
				blue.eb(qvec.back());
			ans/=2;
			res+=ans;
		}
	}
	return res;
}

Compilation message (stderr)

mushrooms.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
mushrooms.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

• Subtask 1: 92.2449 / 100