Submission #304467

#	Time	Username	Problem	Language	Result	Execution time	Memory
304467		arnold518	Counting Mushrooms (IOI20_mushrooms)	C++14	53.30 / 100	12 ms	500 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 = 70;

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=A.size();

	//printf("%d %d\n", p, A.size());

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

	return ans;
}

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:55:8: warning: unused variable 'i' [-Wunused-variable]
   55 |    int i, j;
      |        ^

• Subtask 1: 53.3019 / 100