oj.uz

Submission #54224

# Submission time Handle Problem Language Result Execution time Memory
54224 2018-07-02T21:02:10 Z radoslav11 The Big Prize (IOI17_prize) C++14
20 / 100
 108 ms 25400 KB 
#include <bits/stdc++.h>
#include "prize.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

vector<int> memo[MAXN];

vector<int> query(int i) 
{
	if(memo[i].empty()) memo[i] = ask(i);
	return memo[i];
}

int find_best(int n) 
{
	int i = 0;
	while(i < n)
	{
		auto curr = query(i);
		if(curr[0] == 0 && curr[1] == 0)
			return i;

		int low = i, high = n - 1, mid, ret;
		
		/*for(int l = 0; low + (1 << l) < n; l++)
		{
			if(curr != query(low + (1 << l))) break;
			low += (1 << l);
			high = low + (1 << l);
		}*/

		while(low <= high)
		{
			mid = (low + high) >> 1;
			if(curr == query(mid))
				low = mid + 1, ret = mid;
			else
				high = mid - 1;
		}

		i = ret + 1;
	}

	return -1;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:45:5: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   i = ret + 1;
   ~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24824 KB Output is correct
2 Correct 26 ms 24884 KB Output is correct
3 Correct 25 ms 25088 KB Output is correct
4 Correct 21 ms 25116 KB Output is correct
5 Correct 22 ms 25116 KB Output is correct
6 Correct 26 ms 25116 KB Output is correct
7 Correct 21 ms 25116 KB Output is correct
8 Correct 22 ms 25124 KB Output is correct
9 Correct 22 ms 25124 KB Output is correct
10 Correct 21 ms 25124 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25252 KB Output is correct
2 Correct 21 ms 25252 KB Output is correct
3 Correct 21 ms 25252 KB Output is correct
4 Correct 27 ms 25252 KB Output is correct
5 Correct 22 ms 25252 KB Output is correct
6 Correct 22 ms 25252 KB Output is correct
7 Correct 21 ms 25252 KB Output is correct
8 Correct 23 ms 25252 KB Output is correct
9 Correct 22 ms 25252 KB Output is correct
10 Correct 21 ms 25252 KB Output is correct
11 Correct 25 ms 25252 KB Output is correct
12 Correct 23 ms 25252 KB Output is correct
13 Correct 25 ms 25324 KB Output is correct
14 Correct 26 ms 25324 KB Output is correct
15 Correct 34 ms 25324 KB Output is correct
16 Incorrect 108 ms 25400 KB Incorrect
17 Halted 0 ms 0 KB -