Submission #1295031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295031		ChuanChen	Counting Mushrooms (IOI20_mushrooms)	C++20	91.13 / 100	4 ms	528 KiB

mushrooms

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

const unsigned int OPT = 60;

int ans;
vector<int> A, B;
queue<int> q;

int count_mushrooms(int n) {
	vector<int> m;
	A.push_back(0);
	for(int i = 1; i < n; i++){
		q.push(i);
	}

	while(q.size() && A.size() <= 2){
		int c1 = q.front(); q.pop();
		int verdic = use_machine({c1, A[0]});
		if(verdic == 0) A.push_back(c1);
		else B.push_back(c1);
	}

	while(q.size() && A.size() <= OPT && B.size() <= OPT){
		int c1 = q.front(); q.pop();
		if(q.empty()){
			int verdic = use_machine({c1, A[0]});
			if(verdic == 0) A.push_back(c1);
			else B.push_back(c1);
			break;
		}

		int c2 = q.front(); q.pop();

		int verdic = use_machine({A[0], c1, A[1], c2});
		if(verdic == 0){
			A.push_back(c1);
			A.push_back(c2);
		}
		else if(verdic == 1){
			A.push_back(c1);
			B.push_back(c2);
		}
		else if(verdic == 2){
			B.push_back(c1);
			A.push_back(c2);
		}
		else{
			B.push_back(c1);
			B.push_back(c2);
		}
	}

	while(!q.empty()){
		if(A.size() < B.size()){ //use B
			vector<int> m(min(2*B.size(), 2*q.size()));
			for(int i = 0; i < (int)m.size(); i+=2) m[i] = B[i/2];
			for(int i = 1; i < (int)m.size(); i+=2){
				m[i] = q.front(); q.pop();
			}
			int verdic = use_machine(m);
			ans += (verdic+1)/2;
			if(verdic&1){
				ans--;
				A.push_back(m.back());
			}
			else B.push_back(m.back());
		}
		else{
			vector<int> m(min(2*A.size(), 2*q.size()));
			for(int i = 0; i < (int)m.size(); i+=2) m[i] = A[i/2];
			for(int i = 1; i < (int)m.size(); i+=2){
				m[i] = q.front(); q.pop();
			}
			int verdic = use_machine(m);
			ans += m.size()/2-(verdic+1)/2;
			if(verdic&1) B.push_back(m.back());
			else{
				ans--;
				A.push_back(m.back());
			}
		}
	}

	return A.size()+ans;
}

• Subtask 1: 91.129 / 100