Submission #405655

#	Time	Username	Problem	Language	Result	Execution time	Memory
405655		kshitij_sodani	Counting Mushrooms (IOI20_mushrooms)	C++14	80.43 / 100	13 ms	328 KiB

mushrooms

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
#define ask use_machine

#include "mushrooms.h"

int count_mushrooms(int n) {
	/*pair<int,int> mi={2000000,-1};
	int nn=20000;
	for(int i=2;i<=nn-4;i+=2){
		int cost=(i/2);
		cost+=2;
		int le=((i+3+1)/2);

		cost+=((nn-i-3+le-1))/le;
		mi=min(mi,{cost,i});
	}
	cout<<mi.a<<":"<<mi.b<<endl;
*/
	if(n<=400){
		int ans2=1;
		for(int i=1;i<n;i+=2){
			if(i+1==n){
				ans2+=1-use_machine({0,i});
				continue;
			}
			ans2+=2-use_machine({i,0,i+1});
		}
		return ans2;
	}
	vector<int> aa;
	vector<int> bb;
	vector<int> cc;
	vector<int> dd;
	aa.pb(0);
	for(int i=1;i<3;i++){
		if(ask({0,i})==0){
			aa.pb(i);
		}
		else{
			bb.pb(i);
		}
	}
	//cc=aa;
	//dd=bb;
	int st=0;
	if(aa.size()>=2){
		
	}
	else{
		st=1;
		swap(aa,bb);

	}
	int yy=273;//199;
	for(int i=3;i<yy and i<n;i+=2){
		if(i+1==n){

			if(ask({aa[0],i})==0){
				aa.pb(i);
			}
			else{
				bb.pb(i);
			}
			continue;
		}
		int x=ask({aa[0],i,aa[1],i+1});
		if(x%2==0){
			aa.pb(i+1);
		}
		else{
			bb.pb(i+1);
		}
		x/=2;
		if(x%2==0){
			aa.pb(i);
		}
		else{
			bb.pb(i);
		}
	}
	if(st){
		swap(aa,bb);
	}
	st=0;
	int ans=aa.size();
	if(bb.size()>=aa.size()){
		st=1;
		swap(aa,bb);
	}
	int ind=yy;
	aa.pb(-1);
	while(ind<n){
		vector<int> ss;
		ss.pb(aa[0]);
		int xx=1;
		while(xx<aa.size() and ind<n){
			ss.pb(ind);
			ss.pb(aa[xx]);
			xx++;
			ind++;
		}
		ss.pop_back();
		int aa=ask(ss);
		if(aa%2==1){
			if(st==0){

			}
			else{
				ans++;
			}
		}
		else{
			if(st==0){
				ans++;
			}
		}
		aa/=2;
		ss.pop_back();
		if(st==0){
			ans+=(ss.size()/2)-aa;
		}
		else{
			ans+=aa;
		}
	}



	if(st){
		swap(aa,bb);
	}
	return ans;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:104:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   while(xx<aa.size() and ind<n){
      |         ~~^~~~~~~~~~

• Subtask 1: 80.427 / 100