Submission #1206305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206305		tkm_algorithms	Counting Mushrooms (IOI20_mushrooms)	C++20	92.62 / 100	3 ms	448 KiB

mushrooms

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long

const char nl = '\n';

//string s;
//int use_machine(vector<int> x) {
	//int cnt = 0;
	//for (int i = 1; i < sz(x); ++i)if (s[x[i]] != s[x[i-1]])cnt += 1;
	//return cnt;
//}

int count_mushrooms(int n) {
	int k = 90, res = 1;
	vector<int> a(1), b;
	
	vector<int> x{0, 1};
	int cnt = use_machine(x);
	if (cnt)b.push_back(1);
	else a.push_back(1), res += 1;
	
	if (n > 2) {
		x.clear(); x = {0, 2};
		cnt = use_machine(x);
		if (cnt)b.push_back(2);
		else a.push_back(2), res += 1;
	}
	
	if (n <= 3)return res;
	
	int i = 3;
	while (i+1 < n && sz(a) < k && sz(b) < k) {
		if (sz(a) >= 2) {
			x = {i, a[0], i+1, a[1]};
			cnt = use_machine(x);
			if (cnt%2 == 1)b.push_back(i);
			else a.push_back(i), res += 1;
			if (cnt >= 2)b.push_back(i+1);
			else a.push_back(i+1), res += 1;
			i += 2;
		} else {
			x = {i, b[0], i+1, b[1]};
			cnt = use_machine(x);
			if (cnt%2 == 1)a.push_back(i), res += 1;
			else b.push_back(i);
			if (cnt >= 2)a.push_back(i+1), res += 1;
			else b.push_back(i+1);
			i += 2;
		}
	}
	
	while (i < n) {
		int mn = min(n-i, max(sz(a), sz(b)));
		if (sz(a) > sz(b)) {
			x.clear();
			for (int j = 0; j < mn; ++j) {
				x.push_back(i+j);
				x.push_back(a[j]);
			}
			cnt = use_machine(x);
			if (cnt&1)b.push_back(i);
			else a.push_back(i);
			res += mn-(cnt+1)/2;
		} else {
			x.clear();
			for (int j = 0; j < mn; ++j) {
				x.push_back(i+j);
				x.push_back(b[j]);
			}
			cnt = use_machine(x);
			if (cnt&1)a.push_back(i);
			else b.push_back(i);
			res += (cnt+1)/2;
		}
		i += mn;
	}
	return res;
}

//int main() {
	//cin >> s;
	//cout << count_mushrooms(sz(s));
//}

• Subtask 1: 92.623 / 100