Submission #441867

#	Time	Username	Problem	Language	Result	Execution time	Memory
441867		FSYo	Counting Mushrooms (IOI20_mushrooms)	C++14	80.71 / 100	11 ms	456 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

#ifdef FSYo
#include "stub.cpp"
#endif 

#define cs const
#define pb push_back
using namespace std;
typedef vector<int> vi; 

int count_mushrooms(int n) {
//	srand(time(NULL));
	vi zero, one, re;
	for(int i = 1; i < n; i++) re.pb(i);
	zero.pb(0);
	random_shuffle(re.begin(), re.end());
	int cnt = 0; // include x in one 
	while(re.size()) {
		if(zero.size() >= one.size()) {
			vi q; 
			for(int i = 0; i < zero.size(); i++) {
				if(re.empty()) break;
				q.pb(re.back()), re.pop_back();
				q.pb(zero[i]);
			}
			int t = use_machine(q);
			if(t & 1) one.pb(q[0]);
			else zero.pb(q[0]);
			cnt += (t + 1) / 2; 
		}
		else {
			vi q; 
			for(int i = 0; i < one.size(); i++) {
				if(re.empty()) break;
				q.pb(re.back()), re.pop_back();
				q.pb(one[i]);
			}
			int t = use_machine(q);
			if(t & 1) zero.pb(q[0]);
			else one.pb(q[0]);
			cnt += (q.size() - t) / 2; 
		}
//		cout << cnt << endl;
//		for(int x : zero) cout << x << ' ';cout <<endl;
//		for(int x : one) cout << x << ' ';cout <<endl;
//		for(int x : re) cout << x << ' ';cout <<endl;
	}
	return n - cnt; 
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for(int i = 0; i < zero.size(); i++) {
      |                   ~~^~~~~~~~~~~~~
mushrooms.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int i = 0; i < one.size(); i++) {
      |                   ~~^~~~~~~~~~~~

• Subtask 1: 80.7143 / 100