제출 #1236635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236635		alex_2008	Counting Mushrooms (IOI20_mushrooms)	C++20	75.33 / 100	4 ms	544 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
bool a[N];
bool X[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*int use_machine(vector<int> x) {
	int c = 0;
	for (int i = 1; i < (int)x.size(); i++) {
		if (X[x[i]] != X[x[i - 1]]) c++;
	}
	return c;
}*/
int count_mushrooms(int n) {
	if (n <= 220) {
		int ans = 1;
		for (int j = 1; j < n; j++) {
			if (use_machine({ 0, j }) == 0) {
				ans++;
			}
		}
		return ans;
	}
	else {
		vector<int> inds(n);
		for (int i = 0; i < n; i++) {
			inds[i] = i;
		}
		shuffle(inds.begin() + 1, inds.end(), rng);
		int block = sqrtl(n / 16);
		vector <int> a, b;
		a = { 0 };
		int last = 0;
		for (int j = 1; j <= 2 * block - 1; j++) {
			if (use_machine({ 0, inds[j] }) == 1) b.push_back(inds[j]);
			else a.push_back(inds[j]);
			last = j;
			if ((int)a.size() == block || (int)b.size() == block) break;
		}
		int ans = (int)a.size();
		block = max((int)a.size(), (int)b.size());
		if ((int)a.size() < (int)b.size()) {
			for (int j = last + 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(inds[j + l]);
				}
				int q = use_machine(cur);
				if (q % 2 == 0) {
					b.push_back(cur.back());
					block++;
					j--;
				}
				ans += ((q + 1) / 2);
			}
		}
		else {
			for (int j = last + 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(inds[j + l]);
				}
				int q = use_machine(cur);
				if (q % 2 == 0) {
					a.push_back(cur.back());
					block++;
					j--;
				}
				ans += (sz - ((q + 1) / 2));
			}
		}
		return ans;
	}
}
/*
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> X[i];
	}
	cout << count_mushrooms(n) << "\n";
	for (int c = 1; c <= 100; c++) {
		cout << count_mushrooms(n) << "\n";
	}
}
*/

• Subtask 1: 75.3333 / 100