Submission #430490

#	Time	Username	Problem	Language	Result	Execution time	Memory
430490		alireza_kaviani	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	15 ms	328 KiB

mushrooms

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

const int SQ = 101;

int calc(vector<int> vec , int l , int r){
	int ans = 0;
	for(int i = l ; i < r ; i += SQ - 1){
		vector<int> v = {vec[0]};
		for(int j = i ; j < min(r , i + SQ - 1) ; j++){
			v.push_back(j);
			v.push_back(vec[j - i + 1]);
		}
		ans += v.size() - 1 - use_machine(v);
	}
	return ans / 2;
}

int count_mushrooms(int n) {
	vector<int> A = {0} , B;
	int cntA = 1 , cntB = 0;
	for (int i = 1 ; i < n ; i++){
		vector<int> v = {0 , i};
		int x = use_machine(v);
		if(x == 0){
			cntA++;
			A.push_back(i);
		}
		if(x == 1){
			cntB++;
			B.push_back(i);
		}
		if(cntA >= SQ || cntB >= SQ)	break;
	}
	if(A.size() == SQ){
		cntA += calc(A , A.size() + B.size() , n);
	}
	if(B.size() == SQ){
		cntA += n - A.size() - B.size() - calc(B , A.size() + B.size() , n);
	}
	return cntA;
}

• Subtask 1: 56.7839 / 100