Submission #430507

#	Time	Username	Problem	Language	Result	Execution time	Memory
430507		alireza_kaviani	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	14 ms	300 KiB

mushrooms

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

int SQ = 101;

int calc(vector<int> vec , int l , int r){
	int ans = 0;
	for(int i = l ; i < r ;){
		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]);
		}
		int cnt = (v.size() - 1 - use_machine(v)) / 2;
		ans += cnt;
		i += SQ - 1;
		int x = (r - i + v.size() - 1) / v.size();
		int y = (r - i + v.size() + cnt - 1) / (v.size() + cnt);
		if(x > y + v.size() / 2){
			for(int j = 1 ; j < v.size() ; j += 2){
				vector<int> u = {vec[0] , v[j]};
				if(use_machine(u) == 0){
					vec.push_back(v[j]);
					SQ++;
				}
			}
		}
	}
	return ans;
}

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;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int calc(std::vector<int>, int, int)':
mushrooms.cpp:20:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   if(x > y + v.size() / 2){
      |      ~~^~~~~~~~~~~~~~~~~~
mushrooms.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    for(int j = 1 ; j < v.size() ; j += 2){
      |                    ~~^~~~~~~~~~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:49:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |  if(A.size() == SQ){
      |     ~~~~~~~~~^~~~~
mushrooms.cpp:52:14: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |  if(B.size() == SQ){
      |     ~~~~~~~~~^~~~~

• Subtask 1: 56.7839 / 100