Submission #1149587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149587		PagodePaiva	Counting Mushrooms (IOI20_mushrooms)	C++20	45.20 / 100	3 ms	432 KiB

mushrooms

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

using namespace std;

const int sqr = 100;

int count_mushrooms(int n) {
	vector <int> A, B;
	A.push_back(0);
	for(int i = 1;i < n;i++){
		if(A.size() >= (n+sqr-1)/sqr+1 or B.size() >= (n+sqr-1)/sqr+1) continue;
		int t = use_machine({0, i});
		if(t == 1) B.push_back(i);
		else A.push_back(i);
	}
	int st = max(A.back(), (B.empty() ? -1 : B.back()));
	st++;
	if(st == n) return A.size();
	int typ = (A.size() >= (n+sqr-1)/sqr+1 ? 0 : 1);
	int res = A.size();
	for(int i = st;i < min(n, st+sqr);i++){
		vector <int> query;
		int x = i;
		int con = 0;
		while(x < n){
			query.push_back((typ == 0 ? A[(x-st)/(sqr)] : B[(x-st)/(sqr)]));
			query.push_back(x);
			con += 2;
			x += sqr;
		}
		query.push_back((typ == 0 ? A.back() : B.back()));
		res += (typ == 0 ? (con-use_machine(query))/2 : use_machine(query)/2);
	}
	return res;
}

• Subtask 1: 45.2 / 100