Submission #346145

#	Time	Username	Problem	Language	Result	Execution time	Memory
346145		Ikkyu9541	Counting Mushrooms (IOI20_mushrooms)	C++17	53.55 / 100	11 ms	524 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 < 4*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);
		if(m[0].size()*m[0].size() >= n || m[1].size()*m[1].size() >= n){
			i++;
			goto skip;
		}
	}
	skip:;
	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(")");
			// printf("(%d)", mm);
	
	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]);
			// }
			if(mm == 1)
				ans += use_machine(a)/2;
			else
				ans += (a.size()/2) - (use_machine(a)/2);
			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:47:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if(m[0].size()*m[0].size() >= n || m[1].size()*m[1].size() >= n){
      |      ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mushrooms.cpp:47:62: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |   if(m[0].size()*m[0].size() >= n || m[1].size()*m[1].size() >= n){
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mushrooms.cpp:77:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |   if(i==n-1 || a.size() >=  (mms*2)-1){
      |                ~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 53.5545 / 100