oj.uz

Submission #302578

# Submission time Handle Problem Language Result Execution time Memory
302578 2020-09-18T19:52:11 Z circlethm The Big Prize (IOI17_prize) C++17
20 / 100
 77 ms 384 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 368 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 376 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Incorrect 77 ms 256 KB Incorrect
12 Halted 0 ms 0 KB -