Submission #376381

#	Time	Username	Problem	Language	Result	Execution time	Memory
376381		InternetPerson10	Counting Mushrooms (IOI20_mushrooms)	C++14	75.08 / 100	13 ms	492 KiB

mushrooms

#include "mushrooms.h"
#include <iostream>

using namespace std;

vector<int> nums, a, b;

int count_mushrooms(int n) {
	int A = 1, B = 0, x;
	bool bb = false;
	nums.push_back(0);
	a.push_back(0);
	nums.push_back(0);
	if(n < 210) {
		for(int i = 1; i < n; i++) {
			nums[1] = i;
			if(use_machine(nums) == 1) B++;
			else A++;
		}
		return A;
	}
	for(int i = 1; i < 3; i++) {
		nums[1] = i;
		if(use_machine(nums) == 0) {
			A++;
			a.push_back(i);
		}
		else {
			B++;
			b.push_back(i);
		}
	}
	if(B >= 2) {
		swap(A, B);
		swap(a, b);
		bb = true;
	}
	nums.resize(4);
	nums[0] = a[0];
	nums[2] = a[1];
	for(int i = 3; i < 199; i += 2) {
		nums[1] = i;
		nums[3] = i+1;
		x = use_machine(nums);
		if(x == 3) {
			B += 2;
			b.push_back(i);
			b.push_back(i+1);
		}
		else if(x == 2) {
			A++; B++;
			b.push_back(i);
			a.push_back(i+1);
		}
		else if(x == 1) {
			A++; B++;
			a.push_back(i);
			b.push_back(i+1);
		}
		else {
			A += 2;
			a.push_back(i);
			a.push_back(i+1);
		}
	}	
	if(bb) {
		swap(a, b);
		swap(A, B);
	}
	bb = false;
	// cout << "A: ";
	// for(int i = 0; i < (int)a.size(); i++) cout << a[i] << ' ';
	// cout << "\n" << A << "\nB: ";
	// for(int i = 0; i < (int)b.size(); i++) cout << b[i] << ' ';
	// cout << "\n" << B << "\n";
	if(B >= 100) {
		swap(a, b);
		swap(A, B);
		bb = true;
	}
	nums.resize(199);
	for(int i = 199; i < n; i += 99) {
		for(int j = 0; j < 100; j++) {
			nums[2*j] = a[j];
		}
		if(i + 99 >= n) {
			for(int j = 0; i+j < n; j++) {
				nums[2*j+1] = i+j;
				x = j;
			}
			x++;
			int y = 0;
			for(int j = 0; j < (int)b.size() && x < 99; j++) {
				nums[2*x+1] = b[j];
				x++;
				y++;
				// cout << "Yay assigned " << 2*(x)+1 << " to " << b[j] << '\n';
			}
			for(int j = 0; 100+j < (int)a.size() && x < 99; j++) {
				nums[2*x+1] = a[j+100];
				x++;
				// cout << "Yay assigned " << 2*(x)+1 << " to " << a[j+100] << '\n';
			}
			// for(int i = 0; i < (int)nums.size(); i++) cout << nums[i] << ' ';
			// cout << '\n';
			x = use_machine(nums);
			// cout << "Ooh I got " << x << '\n';
			x /= 2;
			x -= y;
			// cout << "owo i'm left with " << x << '\n';
			B += x;
			A += (n-i) - x;
			// cout << "Ok now it's " << A << ' ' << B << '\n';
		}
		else {
			for(int j = 0; j < 99; j++) {
				nums[2*j+1] = i+j;
			}
			x = use_machine(nums);
			x /= 2;
			B += x;
			A += 99 - x;
		}
	}
	if(bb) {
		swap(a, b);
		swap(A, B);
	}
	return A;
}

• Subtask 1: 75.0831 / 100