Submission #802903

#	Time	Username	Problem	Language	Result	Execution time	Memory
802903		prvocislo	Counting Mushrooms (IOI20_mushrooms)	C++17	80.71 / 100	8 ms	588 KiB

mushrooms

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

int use_machine(vector<int> x);

int count_mushrooms(int n)
{
	int cnt0 = 0; // pocet hribov typu 0 ktore mame
	vector<vector<int> > v(2); // hriby ktorych typ vieme
	v[0].push_back(0);

	vector<int> unk;
	for (int i = 1; i < n; i++) unk.push_back(i);
	random_shuffle(unk.begin(), unk.end());

	while (!unk.empty())
	{
		int id = 0;
		if (v[1].size() > v[0].size()) id = 1;
		vector<int> ask = v[id];
		ask.push_back(unk.back());
		unk.pop_back();
		int all = 0;
		vector<int> nw;
		for (int i = 0; i + 1 < v[id].size(); i++)
		{
			if (unk.empty()) break;
			nw.push_back(unk.back());
			ask.insert(ask.begin() + i * 2 + 1, unk.back());
			unk.pop_back();
			all++;
		}
		int x = use_machine(ask);
		if (x / 2 == 0)
		{
			for (int i : nw) v[id].push_back(i);
		}
		else if (x / 2 == all)
		{
			for (int i : nw) v[id ^ 1].push_back(i);
		}
		else
		{
			if (id == 0) cnt0 += all - (x / 2);
			else cnt0 += x / 2;
		}
		v[id ^ (x & 1)].push_back(ask.back());
	}
	return cnt0 + v[0].size();
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int i = 0; i + 1 < v[id].size(); i++)
      |                   ~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 80.7143 / 100