Submission #364321

#	Time	Username	Problem	Language	Result	Execution time	Memory
364321		Jasiekstrz	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	15 ms	620 KiB

mushrooms

#include<bits/stdc++.h>
#include "mushrooms.h"
#define fi first
#define se second
using namespace std;
const int K=200;
mt19937 gen(2137);
inline int p(int l,int r)
{
	return uniform_int_distribution<int>{l,r}(gen);
}
int count_mushrooms(int n)
{
	int i;
	int ans=1;
	bool xd=false;
	vector<int> tmp;
	vector<int> a={0},b;
	vector<int> tt;
	for(i=1;i<n;i++)
		tmp.push_back(i);
	shuffle(tmp.begin(),tmp.end(),gen);
	for(i=1;i<=K && !tmp.empty();i++)
	{
		if(use_machine((vector<int>){0,tmp.back()}))
			b.push_back(tmp.back());
		else
		{
			a.push_back(tmp.back());
			ans++;
		}
		tmp.pop_back();
	}
	if(b.size()>a.size())
	{
		swap(a,b);
		xd=true;
	}
	while(!tmp.empty())
	{
		tt.clear();
		tt.push_back(a[0]);
		for(i=1;i<a.size() && !tmp.empty();i++)
		{
			tt.push_back(tmp.back());
			tt.push_back(a[i]);
			tmp.pop_back();
		}
		if(xd)
			ans+=use_machine(tt)/2;
		else
			ans+=i-1-use_machine(tt)/2;
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:43:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(i=1;i<a.size() && !tmp.empty();i++)
      |           ~^~~~~~~~~

• Subtask 1: 56.7839 / 100