Submission #302578

#	Time	Username	Problem	Language	Result	Execution time	Memory
302578		circlethm	The Big Prize (IOI17_prize)	C++17	20 / 100	77 ms	384 KiB

prize

#include "prize.h"
#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> vi;

// There is 1 diamond
// There is n - 1 lollipops.

int find_best(int n)
{

	// Binary Search
	// Highest is the highest box THAT IT COULD BE IN. Same for lowest
	int highest = n - 1;
	int lowest = 0;

	while (highest != lowest)
	{
		int current = (highest + lowest) / 2;
		vi answer = ask(current);

		// cout << "Current: " << current << " - Range: (" << lowest << ", " << highest << ") - Query: [" << answer[0] << ", " << answer[1] << "]" << endl;

		if (answer[0] == answer[1] && answer[0] == 0)
		{
			// cout << "Here" << endl;
			// This is it
			highest = current;
			lowest = current;
		}

		if (answer[0] == 1)
		{
			highest = current - 1;
		}
		else if (answer[1] == 1)
		{
			lowest = current + 1;
		}
	}

	return lowest;

	// for(int i = 0; i < n; i++) {
	// 	std::vector<int> res = ask(i);
	// 	if(res[0] + res[1] == 0)
	// 		return i;
	// }
	// return 0;
}

// n boxes (0 to n - 1)
// each with a prize
// v types of prize
// numbered from 1 to b in decreasing order of value

// Prize 1 - Diamond (exactly 1)
// Prize v - lollipop.
// Number of cheaper is much larger than numbe rof expeonsive ones/
// For all t, if there is k types of prize for t - 1, then theres > k^2 prizes of type t.

// You want to win the diamond.
// At the end of the game, you open a box and get the prize

// Before choosing a box, you get to ask Rambox, the host, some questions.
// For eahc question, you choose some box i
// He will answer with an array a containing two integers:
// 1. to the left of box i there are a[0] boxes with a more expensive prize
// 2 To the right of i there are exactly a[1] boxes with a more expensive prize than in box i.

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80