Submission #589047

#	Time	Username	Problem	Language	Result	Execution time	Memory
589047		LIF	Counting Mushrooms (IOI20_mushrooms)	C++14	56.64 / 100	24 ms	508 KiB

mushrooms

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

int count_mushrooms(int n) {
	std::vector <int> m;
	vector<int> a;
	vector<int> b; 
	int aans = 1;
	int bans = 0;
	a.push_back(0);
	
	m.push_back(0);
	bool check[200005];
	for(int i=1;i<200&&i<n;i++)
	{
		m.push_back(i);
		if(use_machine(m) == 1)
		{
			bans++;
			b.push_back(i);
		}
		else
		{
			aans++;
			a.push_back(i);
		}
		m.pop_back();
	}
	m.clear();
	if(b.size()>a.size()) //that means we can use b to compute
	{
		
		for(int i=200;i<n;i+=b.size()-1)
		{	
			int headb = 0;
			int headch = i;
			for(int j=0;j<b.size()*2-1;j++)
			{
				if(j%2==0)
				{
					m.push_back(b[headb]);
					headb++;
				}
				else
				{
					if(headch>=n)break;
					m.push_back(headch);
					check[headch] = true;
					headch++;
				}
			}
			int ans  = use_machine(m);
			ans /=2;
			aans += ans;
			m.clear();
		}
	}
	else
	{
		for(int i=200;i<n;i+=a.size()-1)
		{
			int heada = 0;
			int headch = i;
			for(int j=0;j<a.size()*2-1;j++)
			{
				if(j%2==0)
				{
					m.push_back(a[heada]);
					heada++;
				}
				else
				{
					if(headch>=n)break;
					check[headch]=true;
					m.push_back(headch);
					headch++;
				}
			}
			int ans = use_machine(m);
			ans /=2; //it is the count of b
			int asize = m.size()/2+1;
			aans+= (m.size() - asize - ans);
			m.clear();
		}
	}
	m.clear();
	m.push_back(0);
	for(int i=200;i<n;i++)
	{
		if(check[i] == false)
		{
			m.push_back(i);
			if(use_machine(m) == 0)
			{
				aans++;	
			}
			m.pop_back();
		}
	}
	
	
	return aans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    for(int j=0;j<b.size()*2-1;j++)
      |                ~^~~~~~~~~~~~~
mushrooms.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for(int j=0;j<a.size()*2-1;j++)
      |                ~^~~~~~~~~~~~~

• Subtask 1: 56.6416 / 100