Submission #1206168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206168		tkm_algorithms	Counting Mushrooms (IOI20_mushrooms)	C++20	25 / 100	27 ms	600 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 = sqrt(1+n)+1;
	int res = 1, start = 0;
	vector<int> a(1), b;
	for (int i = 1; i <= min(n-1, 2); ++i) {
		vector<int> x = {0, i};
		int cnt = use_machine(x);
		if (cnt == 0)a.push_back(i), res += 1;
		else b.push_back(i);
	}
	vector<int> newa = a, newb = b;
	if (n <= 3)return res;
	
	bool ok2 = false;
	if (sz(b) == 2)swap(a, b), ok2 = true;
	if (n == 4) {
		vector<int> x = {0, 3};
		if (use_machine(x) == 0)return res+1;
		else return res;
	}
	
	//for (auto i: newa)cout << i << " ";
	//cout << nl;
	
	int i = 3;
	while (i <= n-2) {
		vector<int> x = {i, a[0], i+1, a[1]};
		int cnt = use_machine(x);
		if (cnt == 1) {
			if (ok2)newa.push_back(i), newb.push_back(i+1), res += 1;
			else newb.push_back(i), newa.push_back(i+1), res+=1;
		}
		if (cnt == 2) {
			if (ok2)newa.push_back(i+1), newb.push_back(i), res += 1;
			else newb.push_back(i+1), newa.push_back(i), res += 1;
		}
		if (cnt == 3) {
			if (ok2)newa.push_back(i+1), newa.push_back(i), res += 2;
			else newb.push_back(i+1), newb.push_back(i);
		}
		if (cnt == 0) {
			if (ok2)newb.push_back(i+1), newb.push_back(i);
			else newa.push_back(i+1), newa.push_back(i), res += 2;
		}
		
		i += 2;
		if (sz(newa) == k || sz(newb) == k)break;
	}
	
	if (i < n && sz(newa) < k && sz(newb) < k) {
		vector<int> x = {0, i};
		if (use_machine(x) == 0)newa.push_back(i), res += 1;
		else newb.push_back(i);
		i += 1;
	}
	
	//cout << i << nl;
	
	start = i;
	a = newa, b = newb;
	if (sz(a) < k && sz(b) < k)return res;
	
	bool ok = false;
	if (sz(b) == k)swap(a, b), ok = true;
	
	while (start < n) {
		int mn = min(n-start, k);
		vector<int> x;
		for (i = 0; i < mn; ++i) {
			x.push_back(i+start);
			x.push_back(a[i]);
		}
		int cnt = use_machine(x);
		cnt = (cnt+1)/2;
		cnt = mn-cnt;
		if (ok)cnt = mn-cnt;
		res += cnt;
		start += k;
	}
	return res;
}

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

• Subtask 1: 25 / 100