Submission #1178860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178860		browntoad	Counting Mushrooms (IOI20_mushrooms)	C++20	56.93 / 100	3 ms	428 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

const ll maxn = 1e5+5;
const int bloc = 95;

int count_mushrooms(int n) {
	int ret;

	vector<int> A, B;
	A.pb(0);
	int ptr = 1;
	while(ptr < n){
		vector<int> tp = {0, ptr};
		ret = use_machine(tp);
		if (ret == 0) A.pb(ptr);
		else B.pb(ptr);
		ptr++;
		if (SZ(A) >= bloc || SZ(B) >= bloc) break;
	}
	if (ptr == n){
		return SZ(A);
	}


	int cnt = 0;
	while(ptr < n){
		vector<int> tmp;
		REP(i, bloc){
			if (ptr == n) break;
			if (SZ(A) >= bloc) tmp.pb(A[i]);
			else tmp.pb(B[i]);
			tmp.pb(ptr);
			ptr++;
		}
		ret = use_machine(tmp);
		if (SZ(A) >= bloc){
			cnt += 1-(ret&1);
			
			ret /= 2;
			cnt += (SZ(tmp)/2-1 - ret);
		}
		else{
			cnt += (ret&1);

			ret/=2;
			cnt += ret;
		}
	}
	return cnt + SZ(A);
}

• Subtask 1: 56.927 / 100