Submission #603413

#	Time	Username	Problem	Language	Result	Execution time	Memory
603413		Red_Inside	Counting Mushrooms (IOI20_mushrooms)	C++17	25 / 100	204 ms	660 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=2e5+100,LOG=17,mod=1e9+7;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>

int count_mushrooms(int n)
{
	vector <int> was, fi, se, que;
	int ret = 0;
	was.assign(n + 2, 0);
	was[0] = 1;
	fi.pb(0);
	que.clear();
	que.pb(0);
	que.pb(1);
	ret = use_machine(que);
	if(ret == 1)
	{
		was[1] = 2;
		se.pb(1);
	}
	else
	{
		was[1] = 1;
		fi.pb(1);
	}
	que.clear();
	if(n <= 2)
	{
		return fi.size();
	}
	que.pb(0);
	que.pb(2);
	ret = use_machine(que);
	if(ret == 1)
	{
		was[2] = 2;
		se.pb(2);
	}
	else
	{
		was[2] = 1;
		fi.pb(2);
	}
	for(int iter = 1; iter * 2 - 1 <= n-3; ++iter)
	{
		int pos = rng() % n;
		while(was[pos]) pos = rng() % n;
		if(n - 3 == 2*iter- 1)
		{
			que.clear();
			que.pb(0);
			que.pb(pos);
			ret = use_machine(que);
			if(ret == 1)
			{
				was[pos] = 2;
				se.pb(pos);
			}
			else
			{
				was[pos] = 1;
				fi.pb(pos);
			}
			break;
		}
		was[pos] = 1;
		int pos2 = rng() % n;
		while(was[pos2]) pos2 = rng() % n;
		if(fi.size() >= 2)
		{
			que.clear();
			que.pb(fi[0]);
			que.pb(pos);
			que.pb(fi[1]);
			que.pb(pos2);
			ret = use_machine(que);
			if(ret % 2 == 1)
			{
				was[pos2] = 2;
				se.pb(pos2);
			}
			else
			{
				was[pos2] = 1;
				fi.pb(pos2);
			}
			if(ret / 2 == 1)
			{
				was[pos] = 2;
				se.pb(pos);
			}
			else
			{
				was[pos] = 1;
				fi.pb(pos);
			}
		}
		else
		{
			que.clear();
			que.pb(se[0]);
			que.pb(pos);
			que.pb(se[1]);
			que.pb(pos2);
			ret = use_machine(que);
			if(ret % 2 == 0)
			{
				was[pos2] = 2;
				se.pb(pos2);
			}
			else
			{
				was[pos2] = 1;
				fi.pb(pos2);
			}
			if(ret / 2 == 0)
			{
				was[pos] = 2;
				se.pb(pos);
			}
			else
			{
				was[pos] = 1;
				fi.pb(pos);
			}
		}
	}
	int ans = 0;
	while(true)
	{
		if(se.size() > fi.size())
		{
			int uk = 0;
			que.clear();
			forn(0, i, n-1)
			{
				if(!was[i])
				{
					que.pb(se[uk++]);
					que.pb(i);
					if(uk == se.size()) break;
				}
			}
			if(que.size() == 0) break;
			ret = use_machine(que);
			ans += ret / 2;
			if(ret % 2 == 1)
			{
				fi.pb(que.back());
			}
			else
			{
				se.pb(que.back());
			}
			for(int i = 1; i < que.size(); i += 2)
			{
				was[que[i]] = 1;
			}
		}
		else
		{
			int uk = 0;
			que.clear();
			forn(0, i, n-1)
			{
				if(!was[i])
				{
					que.pb(fi[uk++]);
					que.pb(i);
					if(uk == fi.size()) break;
				}
			}
			if(que.size() == 0) break;
			ret = use_machine(que);
			ans += ((int)que.size()) / 2-1 - (ret / 2);
			if(ret % 2 == 1)
			{
				se.pb(que.back());
			}
			else
			{
				fi.pb(que.back());
			}
			for(int i = 1; i < que.size(); i += 2)
			{
				was[que[i]] = 1;
			}
		}
	}
	return ans + (int)fi.size();
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:168:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |      if(uk == se.size()) break;
      |         ~~~^~~~~~~~~~~~
mushrooms.cpp:182:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |    for(int i = 1; i < que.size(); i += 2)
      |                   ~~^~~~~~~~~~~~
mushrooms.cpp:197:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |      if(uk == fi.size()) break;
      |         ~~~^~~~~~~~~~~~
mushrooms.cpp:211:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |    for(int i = 1; i < que.size(); i += 2)
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 25 / 100