Submission #304475

#	Time	Username	Problem	Language	Result	Execution time	Memory
304475		arnold518	Counting Mushrooms (IOI20_mushrooms)	C++14	55.53 / 100	12 ms	448 KiB

mushrooms

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e4;
const int SQ = 80;

int N;

int query(vector<int> V)
{
	return use_machine(V);
}

int count_mushrooms(int _N)
{
	N=_N;

	vector<int> A, B;
	A.push_back(0);

	int p, ans=0;
	for(p=1; p<N && A.size()<SQ && B.size()<SQ; p++)
	{
		if(query({0, p})) B.push_back(p);
		else A.push_back(p);
	}
	ans=0;
 
	//printf("%d %d\n", p, A.size());

	while(p<N)
	{
		if(A.size()>B.size())
		{
			int i, j;
			vector<int> V;
			for(j=0; p<N && j<SQ; p++, j++)
			{
				V.push_back(A[j]);
				V.push_back(p);
			}
			int t=query(V);
			if(t%2) B.push_back(V.back());
			else A.push_back(V.back());
			ans+=j-t/2-1;
		}
		else
		{
			int i, j;
			vector<int> V;
			for(j=0; p<N && j<SQ; p++, j++)
			{
				V.push_back(B[j]);
				V.push_back(p);
			}
			int t=query(V);
			if(t%2) A.push_back(V.back());
			else B.push_back(V.back());
			ans+=t/2;
		}
	}

	return ans+A.size();
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:40:8: warning: unused variable 'i' [-Wunused-variable]
   40 |    int i, j;
      |        ^
mushrooms.cpp:54:8: warning: unused variable 'i' [-Wunused-variable]
   54 |    int i, j;
      |        ^

• Subtask 1: 55.5283 / 100