Submission #423565

#	Time	Username	Problem	Language	Result	Execution time	Memory
423565		Mazaalai	Counting Mushrooms (IOI20_mushrooms)	C++14	90.76 / 100	11 ms	564 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
    int opt = 1e9, k = 50;
	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(2);
		else b.push_back(2);
	}
	int idx = 3;
	while (idx+1 < n && a.size() < k && b.size() < k) {
		// cout << "OPEN\n";
		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 = a.size();
	while(idx < n) {
		k = max(a.size(), b.size());
		bool O = a.size() >= b.size();
		int st = idx, end = min(n-1, idx + k - 1);
		int len = end - st + 1;
		vector <int> tmp;
		for (int i = 0; i < len; i++) {
			tmp.push_back(i + st);
			if (O)
				tmp.push_back(a[i]);
			else
				tmp.push_back(b[i]);
		}
		int k = use_machine(tmp), k1 = k;
		k = ((k&1)+k)/2;
		if (O) ans += len - k;
		else ans += k;
		
		if (k1 & 1) {
			if (O) b.push_back(idx);
			else {
				a.push_back(idx);
			}
		} else {
			if (!O) b.push_back(idx);
			else {
				a.push_back(idx);
			}
		}
		idx += len;
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:19:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |  while (idx+1 < n && a.size() < k && b.size() < k) {
      |                      ~~~~~~~~~^~~
mushrooms.cpp:19:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |  while (idx+1 < n && a.size() < k && b.size() < k) {
      |                                      ~~~~~~~~~^~~
mushrooms.cpp:5:9: warning: unused variable 'opt' [-Wunused-variable]
    5 |     int opt = 1e9, k = 50;
      |         ^~~

• Subtask 1: 90.7631 / 100