Submission #306881

#	Time	Username	Problem	Language	Result	Execution time	Memory
306881		egorlifar	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	256 KiB

mushrooms

#include "mushrooms.h"
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>

using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 



int ask(vector<int> order) {
	return use_machine(order);
}

int count_mushrooms(int n) {
	vector<int> st, st1;
	st.pb(0);
	int cnt0 = 1;
	int cnt1 = 0;
	int it = 1;
	while (it != n) {
		if (sz(st) > sz(st1)) {
			int can = sz(st);
			vector<int> order;
			int cur = 0;
			int realmen = 0;
			vector<int> ids;
			while (it < n && can) {
				order.pb(st[cur]);
				can--;
				realmen++;
				ids.pb(it);
				order.pb(it);
				it++;
			}
			int d = ask(order);
			int f = d / 2;
			cnt1 += f;
			cnt0 += (realmen - 1 - f);
			if (d & 1) {
				cnt1++;
				st1.pb(ids.back());
			} else {
				cnt0++;
				st.pb(ids.back());
			}
		} else {
			int can = sz(st1);
			vector<int> order;
			int cur = 0;
			int realmen = 0;
			vector<int> ids;
			while (it < n && can) {
				order.pb(st1[cur]);
				can--;
				realmen++;
				ids.pb(it);
				order.pb(it);
				it++;
			}
			int d = ask(order);
			int f = d / 2;
			cnt0 += f;
			cnt1 += (realmen - 1 - f);
			if (d & 1) {
				cnt0++;
				st.pb(ids.back());
			} else {
				cnt1++;
				st1.pb(ids.back());
			}
		}
	}	
	return cnt0;	
}

• Subtask 1: 0 / 100