Submission #1240344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240344		AMnu	Counting Mushrooms (IOI20_mushrooms)	C++20	100 / 100	3 ms	452 KiB

mushrooms

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

int N, P = 1, ans = 1;
vector <int> A[2];

void pre() {
	if (A[0].size() >= 3) {
		int c = use_machine({P,0,P+1,A[0][1],P+2,A[0][2]});
		A[c&1].push_back(P);
		if (c < 2) {
			A[0].push_back(P+1);
			A[0].push_back(P+2);
		}
		else if (c > 3) {
			A[1].push_back(P+1);
			A[1].push_back(P+2);
		}
		else if (A[1].size() >= 2) {
			c = use_machine({A[1][0],P+1,A[1][1],A[0][0],P+2,A[0][1],P+3,A[0][2],P+4}) - 1;
			A[~c>>2&1].push_back(P+1);
			A[c>>2&1].push_back(P+2);
			A[c>>1&1].push_back(P+3);
			A[c&1].push_back(P+4);
			P+=2;
		}
		else {
			c = use_machine({P+1,0,P+2,A[0][1],P+3,A[0][2]});
			A[c&1].push_back(P+1);
			A[~c&1].push_back(P+2);
			A[c>2].push_back(P+3);
			P++;
		}
		P+=3;
		return;
	}
	if (A[1].size() >= 3) {
		int c = use_machine({P,A[1][0],P+1,A[1][1],P+2,A[1][2]});
		A[~c&1].push_back(P);
		if (c < 2) {
			A[1].push_back(P+1);
			A[1].push_back(P+2);
		}
		else if (c > 3) {
			A[0].push_back(P+1);
			A[0].push_back(P+2);
		}
		else if (A[0].size() >= 2) {
			c = use_machine({A[0][0],P+1,A[0][1],A[1][0],P+2,A[1][1],P+3,A[1][2],P+4}) - 1;
			A[c>>2&1].push_back(P+1);
			A[~c>>2&1].push_back(P+2);
			A[~c>>1&1].push_back(P+3);
			A[~c&1].push_back(P+4);
			P+=2;
		}
		else {
			c = use_machine({P+1,A[1][0],P+2,A[1][1],P+3,A[1][2]});
			A[~c&1].push_back(P+1);
			A[c&1].push_back(P+2);
			A[c<3].push_back(P+3);
			P++;
		}
		P+=3;
		return;
	}
	if (A[0].size() >= 2) {
		int c = use_machine({P,0,P+1,A[0][1]});
		A[c&1].push_back(P);
		A[c>>1&1].push_back(P+1);
		P+=2;
		return;
	}
	if (A[1].size() >= 2) {
		int c = use_machine({P,A[1][0],P+1,A[1][1]});
		A[~c&1].push_back(P);
		A[~c>>1&1].push_back(P+1);
		P+=2;
		return;
	}
	int c = use_machine({P,0});
	A[c].push_back(P);
	P++;
	return;
}

int count_mushrooms(int n) {
	N = n;
	A[0].push_back(0);
	if (N > 10000) {
		while (P < 200) {
			pre();
		}
		ans = A[0].size();
	}
	while (P < N) {
		if (A[0].size() > A[1].size()) {
			vector <int> m;
			for (int x : A[0]) {
				m.push_back(P);
				m.push_back(x);
				P++;
				if (P == N) {
					break;
				}
			}
			int c = use_machine(m);
			ans += m.size()/2 - (c+1)/2;
			A[c&1].push_back(m[0]);
		}
		else {
			vector <int> m;
			for (int x : A[1]) {
				m.push_back(P);
				m.push_back(x);
				P++;
				if (P == N) {
					break;
				}
			}
			int c = use_machine(m);
			ans += (c+1)/2;
			A[~c&1].push_back(m[0]);
		}
	}
	return ans;
}

• Subtask 1: 100 / 100