Submission #304436

#	Time	Username	Problem	Language	Result	Execution time	Memory
304436		arnold518	Counting Mushrooms (IOI20_mushrooms)	C++14	0 / 100	16 ms	384 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 = 200;

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();

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

	return ans;
}

• Subtask 1: 0 / 100