Submission #346119

#	Time	Username	Problem	Language	Result	Execution time	Memory
346119		Ikkyu9541	Counting Mushrooms (IOI20_mushrooms)	C++17	53.18 / 100	12 ms	492 KiB

mushrooms

#include "mushrooms.h"
#include <vector>
#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

int count_mushrooms(int n) {
	bool b[100005];
	int ans = 1;
	b[0] = 0;
	vector<int> a;
	a.push_back(0);
	a.push_back(0);
	vector<int> m[2];
	m[0].push_back(0);
	int i;

	if(n < 200){
		for (i = 1; i < n; i++){
			a[0] = i-1;	a[1] = i;
			int u = use_machine(a);
			if(u){
				b[i] = !b[i-1];
			}
			else{
				b[i] = b[i-1];
			}
			if(b[i] == 0) ans++;
		}
		return ans;
	}

	for (i = 1; i*i < n; i++){
		a[0] = i-1;	a[1] = i;
		int u = use_machine(a);
		if(u){
			
			b[i] = !b[i-1];
		}
		else{
			b[i] = b[i-1];
		}
		if(b[i] == 0) ans++;
		m[b[i]].push_back(i);
	}
	a.clear();
	int mm;
	if(m[0].size() > m[1].size()) mm = 0;
	else mm = 1;
			/*
			printf("(");
			for(int j=0; j<m[0].size(); j++){
				printf("%d, ", m[0][j]);
			}
			printf(")");
			printf("(");
			for(int j=0; j<m[1].size(); j++){
				printf("%d, ", m[1][j]);
			}
			printf(")");*/
	
	int mms = m[mm].size();
	int l = 0;
	a.push_back(m[mm][l%m[mm].size()]); l++;

	while(i<n){
		a.push_back(i);
		a.push_back(m[mm][l%m[mm].size()]); l++;
		if(i==n-1 || a.size() >=  (mms*2)-1){
			/*
			printf("[");
			for(int j=0; j<a.size(); j++){
				printf("%d, ", a[j]);
			}*/
			int ta;
			if(mm == 1)
				ta = use_machine(a)/2;
			else
				ta = (a.size()/2) - (use_machine(a)/2);
			ans += ta;
			// printf(":%d]", ta);
			a.clear();
			l = 0;
			a.push_back(m[mm][l%m[mm].size()]); l++;
		}
		i++;
		
	}

	


	return ans;
}



/*

0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1


0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
*/

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:71:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |   if(i==n-1 || a.size() >=  (mms*2)-1){
      |                ~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 53.1765 / 100