Submission #418607

#	Time	Username	Problem	Language	Result	Execution time	Memory
418607		20160161simone	Counting Mushrooms (IOI20_mushrooms)	C++14	56.36 / 100	11 ms	308 KiB

mushrooms

#include "mushrooms.h"
//use_machine
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=2e4+10;
vector<ll> a,b;// 
int count_mushrooms(int n){
	a.push_back(0);
	for(ll i=1;i<=sqrt(n)*2-1;i++){
		vector<ll> t;
		t.push_back(0);
		t.push_back(i);
		ll op=use_machine(t);
		if(op==1) b.push_back(i);
		else a.push_back(i);
	}
//	cout<<"___";
//	for(ll i=0;i<a.size();i++) printf("%lld ",a[i]);cout<<endl;
//	for(ll i=0;i<b.size();i++) printf("%lld ",b[i]);cout<<endl;
	ll top=sqrt(n)*2-1;
	if(a.size()>=sqrt(n)){
		ll ans=b.size();
		while(top<n-1){
			vector<ll> t; 
			for(ll i=0;i<a.size();i++){
				t.push_back(a[i]);
				if(top<n-1) t.push_back(++top); 
			}
			ll op=use_machine(t);
			if(op%2==0) a.push_back(t[t.size()-1]); 
			ans+=(op+1)/2;
		}
		return n-ans;
	}
	else{
		ll ans=a.size();
		while(top<n-1){
			vector<ll> t; 
			for(ll i=0;i<b.size();i++){
				t.push_back(b[i]);
				if(top<n-1) t.push_back(++top); 
			}
			ll op=use_machine(t);
			if(op%2==0) b.push_back(t[t.size()-1]); 
			ans+=(op+1)/2;
		}
		return ans;
	}
	return a.size();
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:26:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    for(ll i=0;i<a.size();i++){
      |               ~^~~~~~~~~
mushrooms.cpp:40:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(ll i=0;i<b.size();i++){
      |               ~^~~~~~~~~

• Subtask 1: 56.3591 / 100