Submission #1075729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075729		Hugo1729	Counting Mushrooms (IOI20_mushrooms)	C++17	56.78 / 100	7 ms	600 KiB

mushrooms

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

const int S = 190;

int bruteforce(int n){
	int ans=1;
	for (int i = 1; i < n; i+=2){
		vector<int> m;
		if(i==n-1)m={0,i};
		else m={i,0,i+1};
		ans+=m.size()-use_machine(m)-1;
	}
 
	// cout << "A: " << ans <<'\n';
 
	return ans;
}

int count_mushrooms(int n) {
	if(n<S+20)return bruteforce(n);

	vector<int> sus(S,0);

	for(int i=1;i<S;i++){
		sus[i]=sus[i-1];
		if(use_machine({i-1,i}))sus[i]^=1;
	}

	queue<int> q;
	for(int i=S;i<n;i++)q.push(i);

	vector<int> A,B;

	for(int i=0;i<S;i++){
		if(sus[i])B.push_back(i);
		else A.push_back(i);
	}

	int ans=A.size();

	
	while(!q.empty()){
		vector<int> m;

		if(A.size()>=B.size()){
			for(int i=0;i<A.size()&&!q.empty();i++){
				m.push_back(q.front());q.pop();
				m.push_back(A[i]);
			}
			int temp=use_machine(m);
			ans+=(m.size()/2)-((temp+1)/2);
		}else{
			for(int i=0;i<B.size()&&!q.empty();i++){
				m.push_back(q.front());q.pop();
				m.push_back(B[i]);
			}
			int temp=use_machine(m);
			ans+=((temp+1)/2);
		}
	}

	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(int i=0;i<A.size()&&!q.empty();i++){
      |                ~^~~~~~~~~
mushrooms.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int i=0;i<B.size()&&!q.empty();i++){
      |                ~^~~~~~~~~

• Subtask 1: 56.7839 / 100