Submission #1207185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207185		I_am_Polish_Girl	Counting Mushrooms (IOI20_mushrooms)	C++20	56.64 / 100	4 ms	512 KiB

mushrooms

#include "mushrooms.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;


mt19937 rnd(1488);

int rnd_(int n)
{
	int x = rnd();

	x = abs(x);

	x %= n;

	return x;
}


int count_mushrooms(int n) {
	if (n <= 200) {
		int col = 1;

		for (int i = 1; i < n; i++) {
			if (use_machine({ 0 , i }) == 0)
				col++;
		}

		return col;
	}

	vector <int> ind(n);


	for (int i = 0; i < n; i++) {
		ind[i] = i;
	}

	random_shuffle(ind.begin() + 1, ind.end() , rnd_);

	vector <int> a;
	vector <int> b;

	a.push_back(0);

	int sq = sqrt(n);

	sq = 99;

	int ind_ = -1;

	for (int i = 1; i < n; i++) {

		if ((a.size() >= 3) and (i + 1 < n))
		{
			int i1 = ind[i];
			int i2 = ind[i + 1];

			int x = use_machine({ a[0] , i1 , a[1] , i2 , a[2] });

			if (x == 0)
			{
				a.push_back(i1);
				a.push_back(i2);
			}

			if (x == 4)
			{
				b.push_back(i1);
				b.push_back(i2);
			}

			if (x == 2)
			{
				if (use_machine({ 0 , i1 }) == 0)
				{
					a.push_back(i1);

					b.push_back(i2);
				}
				else
				{
					a.push_back(i2);

					b.push_back(i1);
				}
			}
			i++;
		}
		else
		{
			if ((b.size() >= 3) and (i + 1 < n))
			{
				int i1 = ind[i];
				int i2 = ind[i + 1];

				int x = use_machine({ b[0] , i1 , b[1] , i2 , b[2] });

				if (x == 0)
				{
					b.push_back(i1);
					b.push_back(i2);
				}

				if (x == 4)
				{
					a.push_back(i1);
					a.push_back(i2);
				}

				if (x == 2)
				{
					if (use_machine({ 0 , i1 }) == 0)
					{
						a.push_back(i1);

						b.push_back(i2);
					}
					else
					{
						a.push_back(i2);

						b.push_back(i1);
					}
				}
				i++;
			}
			else
			{
				if (use_machine({ 0 , ind[i] }) == 0)
					a.push_back(ind[i]);
				else
					b.push_back(ind[i]);
			}
		}

		if (max(a.size(), b.size()) >= sq) {
			ind_ = i + 1;
			break;
		}
	}

	bool f = 0;
	int col = a.size();

	if (b.size() >= a.size()) {
		f = 1;

		swap(a, b);
	}


	vector <int> u;
	for (int i = ind_; i < n; i++) {
		u.push_back(ind[i]);

		if ((u.size() == a.size() - 1) or (i == n - 1)) {
			vector <int> q;
			int i__ = 0;

			for (int i = 0; i < u.size(); i++) {
				q.push_back(a[i__]);
				i__++;

				q.push_back(u[i]);
			}

			q.push_back(a[i__]);
			i__++;

			int r = use_machine(q);

			r /= 2;


			if (f == 0)
				col += u.size() - r;
			else
				col += r;

			u.clear();
		}
	}

	return col;
}

• Subtask 1: 56.6416 / 100