Submission #346196

#	Time	Username	Problem	Language	Result	Execution time	Memory
346196		Ikkyu9541	Counting Mushrooms (IOI20_mushrooms)	C++17	53.68 / 100	14 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;
	}

	a.push_back(0);
	for (i = 2; i*i < 4*n; i+=2){
		a[0] = i-1;	a[1] = 0; a[2] = i;
		int u = use_machine(a);
		if(u == 2){
			b[i-1] = 1;
			b[i] = 1;
			m[1].push_back(i-1);
			m[1].push_back(i);
		}
		else if(u == 1){
			a.resize(2);
			if(use_machine(a) == 0){
				b[i-1] = 0;
				b[i] = 1;
				m[0].push_back(i-1);
				m[1].push_back(i);
			}
			else{
				b[i-1] = 1;
				b[i] = 0;
				m[0].push_back(i);
				m[1].push_back(i-1);
			}
			a.resize(3);
		}
		else{
			b[i-1] = 0;
			b[i] = 0;
			m[0].push_back(i-1);
			m[0].push_back(i);
		}
		if(b[i] == 0) ans++;
		if(b[i-1] == 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:70:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   if(m[0].size()*m[0].size() >= n || m[1].size()*m[1].size() >= n){
      |      ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mushrooms.cpp:70:62: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |   if(m[0].size()*m[0].size() >= n || m[1].size()*m[1].size() >= n){
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mushrooms.cpp:100:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |   if(i==n-1 || a.size() >=  (mms*2)-1){
      |                ~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 53.6817 / 100