Submission #1236601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236601		alex_2008	Counting Mushrooms (IOI20_mushrooms)	C++20	53.55 / 100	3 ms	432 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
int count_mushrooms(int n) {
	if (n <= 100) {
		int ans = 1;
		for (int j = 1; j < n; j++) {
			if (use_machine({ 0, j }) == 0) {
				ans++;
			}
		}
		return ans;
	}
	else {
		int block = sqrtl(n);
		vector <int> a, b;
		a = { 0 };
		for (int j = 1; j <= 2 * block; j++) {
			if (use_machine({ 0, j }) == 1) b.push_back(j);
			else a.push_back(j);
		}
		int ans = (int)a.size();
		if ((int)a.size() < (int)b.size()) {
			for (int j = 2 * block + 1; j < n; j += block) {
				vector <int> cur = {};
				for (int l = 0; l < min(n - j, block); l++) {
					cur.push_back(b[l]);
					cur.push_back(j + l);
				}
				cur.push_back(b[block]);
				ans += (use_machine(cur) / 2);
			}
		}
		else {
			for (int j = 2 * block + 1; j < n; j += block) {
				vector <int> cur = {};
				int sz = 0;
				for (int l = 0; l < min(n - j, block); l++) {
					sz++;
					cur.push_back(a[l]);
					cur.push_back(j + l);
				}
				cur.push_back(a[block]);
				ans += (sz - (use_machine(cur) / 2));
			}
		}
		return ans;
	}
}

• Subtask 1: 53.5545 / 100