Submission #1295050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295050		julia_08	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	4 ms	428 KiB

mushrooms

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

using namespace std;

int get_ans(int sz, int ans, int x){
	if(x == 0) return sz / 2 - (ans + 1) / 2;
	return (ans + 1) / 2;
}

int count_mushrooms(int n){

	int x = 0;

	vector<int> pos[2];

	int k = 80;

	pos[x].push_back(0);

	int tot = 1;

	int last = 0;

	for(int i=1; i<n; i++){

		if((int) pos[x].size() >= k) break;

		vector<int> ask;

		int sz = (int) pos[x].size();

		for(int j=i; j<min(i + sz, n); j++){
			ask.push_back(pos[x][j - i]);
			ask.push_back(j);
		}

		i = min(i + sz, n) - 1;

		int cur = use_machine(ask);

		tot += get_ans((int) ask.size(), cur, x);

		if(cur % 2 != x){
			pos[1 - x].push_back(i);
		} else pos[x].push_back(i);

		if((int) pos[1 - x].size() > (int) ask.size()){
			x = 1 - x;
			ask = pos[x];
		}

		last = i;

	}

	last ++;

	while(last < n){

		vector<int> ask;

		for(int i=0; i<pos[x].size(); i++){

			if(last == n) continue;

			ask.push_back(pos[x][i]);
			ask.push_back(last++);

		}

		tot += get_ans((int) ask.size(), use_machine(ask), x);

	}

	return tot;

}

• Subtask 1: 0 / 100