Submission #431816

#	Time	Username	Problem	Language	Result	Execution time	Memory
431816		MeGustaElArroz23	Counting Mushrooms (IOI20_mushrooms)	C++14	77.13 / 100	15 ms	308 KiB

mushrooms

#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <string>
#include "mushrooms.h"

///////////////////////

#include "mushrooms.h"
#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;

void debug(vi v){
	//for (int x:v) cerr<<x << ' ';
	//cerr<<'\n';
}

int query(vi v){
	//cerr<<"q: ";
	//for (int x:v) cerr << x << ' ';
	//cerr<<'\n'<<"   "<<use_machine(v)<<'\n';
	return use_machine(v);
}

int count_mushrooms( int n) {
	int sol=0;

	bool cambio=0;

	vi A={0};
	vi B;

	int x=query(vi{0,1});
	if (x) B.push_back(1);
	else A.push_back(1);

	if (n==2) return A.size();

	int y=query(vi{0,2});
	if (y) B.push_back(2);
	else A.push_back(2);

	if (n==3) return A.size();
	
	if (A.size()>=2) 1+1;//sol=A.size();
	else{
		cambio=true;
		swap(A,B);
		//sol=A.size();
	}

	debug(A);
	debug(B);

	for (int i=2;i<187 and 2*i<n;i++){
		int a=query(vi{A[0],2*i-1,A[1],2*i});
		if (a==0){
			A.push_back(2*i-1);
			A.push_back(2*i);
		}
		else if (a==1){
			A.push_back(2*i-1);
			B.push_back(2*i);
		}
		else if (a==2){
			B.push_back(2*i-1);
			A.push_back(2*i);
		}
		else if (a==3){
			B.push_back(2*i-1);
			B.push_back(2*i);
		}
	}

	if (A.size()<B.size()){
		cambio=not cambio;
		swap(A,B);
	}

	//debug(A);
	//debug(B);

	sol=A.size();

	int ac=A[A.size()-1]+1;
	if (B.size()) ac=max(A[A.size()-1],B[B.size()-1])+1;
	int j=0;

	vi v;

	while (ac<n){
		if (j==A.size()-1){
			v.push_back(A[j]);
			sol+=v.size()/2-query(v)/2;
			v=vi(0);
			j=0;
			continue;
		}
		v.push_back(A[j]);
		v.push_back(ac);
		j++;
		ac++;
	}
	v.push_back(A[A.size()-1]);
	if (v.size()>1) sol+=v.size()/2-query(v)/2;

	if (cambio) sol=n-sol;
	return sol;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:57:20: warning: statement has no effect [-Wunused-value]
   57 |  if (A.size()>=2) 1+1;//sol=A.size();
      |                   ~^~
mushrooms.cpp:104:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   if (j==A.size()-1){
      |       ~^~~~~~~~~~~~

• Subtask 1: 77.1331 / 100