Submission #772348

#	Time	Username	Problem	Language	Result	Execution time	Memory
772348		ono_de206	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	2 ms	308 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int bl = 138;

int solve(int x, int y, int n) {
	queue<int> m;
	for(int i = 0; i < n; i++) {
		if(i != x && i != y) m.push(i);
	}
	vector<int> a, b;
	a.pb(x); a.pb(y);
	for(int i = 0; i < bl && m.size(); i++) {
		int cx = m.front(); m.pop();
		int cy = -1;
		if(m.size()) {
			cy = m.front(); m.pop();
		}
		int tmp = 0;
		if(cy == -1) {
			tmp = use_machine(vector<int>{x, cx});
		} else {
			tmp = use_machine(vector<int>{x, cy, y, cx});
		}
		if(tmp % 2 == 0) a.pb(cx);
		else b.pb(cx);

		if(~cy) {
			if(tmp <= 1) a.pb(cy);
			else b.pb(cy);
		}
	}
	bool did = 0;
	if(b.size() > a.size()) {
		swap(a, b);
		did = 1;
	}
	int id = 0;
	vector<int> ask;
	int ret = a.size();
	while(m.size()) {
		if(id == a.size()) {
			ret += (use_machine(ask) + 1) / 2;
			ask.clear();
			id = 0;
		}
		int now = m.front(); m.pop();
		ask.pb(a[id++]);
		ask.pb(now);
	}
	if(ask.size()) {
		ret += (use_machine(ask) + 1) / 2;
	}
	if(did) ret = n - ret;
	return ret;
}

int count_mushrooms(int n) {
	if(n == 2) return n - use_machine(vector<int>{0, 1});
	vector<int> a, b;
	int A = 1;
	a.pb(0);
	if(use_machine(vector<int>{0, 1}) == 1) b.pb(1);
	else a.pb(1);
	if(use_machine(vector<int>{0, 2}) == 1) b.pb(2);
	else a.pb(2);
	if(a.size() >= 2) {
		A = solve(a[0], a[1], n);
	} else {
		A = n - solve(b[0], b[1], n);
	}
	return A;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int solve(int, int, int)':
mushrooms.cpp:59:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if(id == a.size()) {
      |      ~~~^~~~~~~~~~~

• Subtask 1: 0 / 100