Submission #1207166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207166		I_am_Polish_Girl	Counting Mushrooms (IOI20_mushrooms)	C++20	56.64 / 100	3 ms	508 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;


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;
	}

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

	a.push_back(0);

	int sq = sqrt(n);

	sq = 100;

	int ind_ = -1;

	for (int i = 1; i < n; i++) {
		if (use_machine({ 0 , 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() == sq) {
		f = 1;

		swap(a, b);
	}


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

		if ((u.size() == sq - 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