제출 #1234274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234274		SpyrosAliv	Counting Mushrooms (IOI20_mushrooms)	C++20	56.93 / 100	3 ms	428 KiB

mushrooms

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

const int BLOCK = 100;

int count_mushrooms(int n) {
	if (n < 226) {
		int tot = 1;
		for (int i = 2; i < n; i+=2) {
			tot += 2 - use_machine({i-1, 0, i});
		}
		if (n % 2 == 0) {
			tot += 1 - use_machine({0, n-1});
		}
		return tot;
	}
	vector<int> a, b;
	a.push_back(0);
	int lst = 0;
	for (int i = 1; i < 2*BLOCK; i++) {
		int isA = !use_machine({0, i});
		if (isA) {
			a.push_back(i);
		}
		else b.push_back(i);
		lst = i;
		if (max((int)a.size(), (int)b.size()) == BLOCK) break;
	}
	vector<int> willUse;
	bool usingA = true;
	if (a.size() == BLOCK) {
		willUse = a;
		usingA = true;
	}
	else {
		willUse = b;
		usingA = false;
	}
	int ans = a.size();
	for (int i = lst + 1; i < n; i += BLOCK) {
		vector<int> qr;
		int inQ = 0;
		for (int j = i; j < min(n, i + BLOCK); j++) {
			qr.push_back(willUse[j - i]);
			qr.push_back(j);
			inQ++;
		}
		int tot = use_machine(qr);
		if (usingA) {
			int totB = 0;
			if (tot % 2) {
				totB = 1;
				tot--;
			}
			totB += tot / 2;
			ans += inQ - totB;
		}
		else {
			int totA = 0;
			if (tot % 2) {
				totA = 1;
				tot--;
			}
			totA += tot / 2;
			ans += totA;
		}
	}
	return ans;
}

• Subtask 1: 56.927 / 100