oj.uz

Submission #304436

# Submission time Handle Problem Language Result Execution time Memory
304436 2020-09-21T11:09:50 Z arnold518 Counting Mushrooms (IOI20_mushrooms) C++14
0 / 100
 16 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Incorrect 16 ms 256 KB Too many total array sizes as queries.
7 Halted 0 ms 0 KB -