Submission #398393

#	Time	Username	Problem	Language	Result	Execution time	Memory
398393		kevinxiehk	Counting Mushrooms (IOI20_mushrooms)	C++17	56.64 / 100	14 ms	328 KiB

mushrooms

#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;
int count_mushrooms(int n) {
	vector<int> m;
	vector<int> a, b;
	int id = 1;
	a.emplace_back(0);
	while(max(a.size(), b.size()) <= min(99, (int)sqrt(n)) && id < n) {
		int t = use_machine({0, id});
		if(t == 1) {
			b.emplace_back(id);
		}
		else a.emplace_back(id);
		id++;
	}
	int ans = a.size();
	if(a.size() > b.size()) {
		for(int i = id; i < n; i += a.size() - 1) {
			int l = i, r = min(n - 1, (int)(i + a.size() - 2));
			m.clear();
			m.emplace_back(a[0]);
			for(int j = l; j <= r; j++) {
				m.emplace_back(j);
				m.emplace_back(a[j - l + 1]);
			}
			int t = use_machine(m);
			ans += (r - l + 1) - (t / 2);
		}
	}
	else {
		for(int i = id; i < n; i += b.size() - 1) {
			int l = i, r = min(n - 1, (int)(i + b.size() - 2));
			m.clear();
			m.emplace_back(b[0]);
			for(int j = l; j <= r; j++) {
				m.emplace_back(j);
				m.emplace_back(b[j - l + 1]);
			}
			int t = use_machine(m);
			ans += (t / 2);
		}
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:9:32: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'const int' [-Wsign-compare]
    9 |  while(max(a.size(), b.size()) <= min(99, (int)sqrt(n)) && id < n) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 56.6416 / 100