Submission #423535

#	Time	Username	Problem	Language	Result	Execution time	Memory
423535		Mazaalai	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	1 ms	200 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
    int opt = 1e9, kk;
    for (int k = 1; k <= n; k++) {
        int cur = (2 * k - 2 + ceil((n - 2 * k - 1) / k));
        if (cur < opt) {
            opt = cur;
            kk = k;
        }
    }
	int k = kk;
	vector <int> a(1, 0), b;
	{
		int res = use_machine({0, 1});
		if (res == 0) a.push_back(1);
		else b.push_back(1);
	}
	if (n == 2) return a.size();
	{ 
		int res = use_machine({0, 2});
		if (res == 0) a.push_back(1);
		else b.push_back(1);
	}
	int idx = 3;
	while (a.size() < k && b.size() < k) {
		int x, y;
		if (a.size() >= 2) {
			x = a[0], y = a[1];
		} else {
			x = b[0], y = b[1];
		}
		int val = use_machine({idx, x, idx+1, y});
		if (a.size() >= 2) {
			if (val == 0) {
				a.push_back(idx);
				a.push_back(idx+1);
			}
			if (val == 1) {
				b.push_back(idx);
				a.push_back(idx+1);
			}
			if (val == 2) {
				a.push_back(idx);
				b.push_back(idx+1);
			}
			if (val == 3) {
				b.push_back(idx);
				b.push_back(idx+1);
			}
		} else {
			if (val == 0) {
				b.push_back(idx);
				b.push_back(idx+1);
			}
			if (val == 1) {
				a.push_back(idx);
				b.push_back(idx+1);
			}
			if (val == 2) {
				b.push_back(idx);
				a.push_back(idx+1);
			}
			if (val == 3) {
				a.push_back(idx);
				a.push_back(idx+1);
			}
		}
		idx+=2;
	}
	int ans = 0;
	bool x = 1;
	if (a.size() < k) {
		x = 0;
		swap(a, b);
		// cout << "Swap\n";
	}
	while(idx < n) {
		int st = idx, end = min(n-1, idx + k - 1);
		int len = end - st + 1;
		// cout << "OPEN: " << st << ' ' << end << ' ' << len << "\n";
		vector <int> tmp;
		for (int i = 0; i < len; i++) {
			tmp.push_back(i + st);
			tmp.push_back(a[i]);
		}
		int k = use_machine(tmp);
		k = ((k&1)+k)/2;
		ans += len - k;
		idx += len;
	}
	// cout << a.size() << ' ' << b.size() << ' ' << ans << '\n';
	return !x ? n - ans - a.size() : a.size() + ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:27:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |  while (a.size() < k && b.size() < k) {
      |         ~~~~~~~~~^~~
mushrooms.cpp:27:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |  while (a.size() < k && b.size() < k) {
      |                         ~~~~~~~~~^~~
mushrooms.cpp:74:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |  if (a.size() < k) {
      |      ~~~~~~~~~^~~
mushrooms.cpp:80:36: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |   int st = idx, end = min(n-1, idx + k - 1);
      |                                ~~~~^~~

• Subtask 1: 0 / 100