oj.uz

Submission #54226

# Submission time Handle Problem Language Result Execution time Memory
54226 2018-07-02T21:03:38 Z radoslav11 The Big Prize (IOI17_prize) C++14
20 / 100
 121 ms 50716 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];
int Q = 0;

vector<int> query(int i) 
{
	if(memo[i].empty()) memo[i] = ask(i), Q++;
	if(Q == 10000) assert(false);
	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:47: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 26 ms 24824 KB Output is correct
2 Correct 24 ms 24884 KB Output is correct
3 Correct 23 ms 24924 KB Output is correct
4 Correct 27 ms 25228 KB Output is correct
5 Correct 28 ms 25228 KB Output is correct
6 Correct 28 ms 25228 KB Output is correct
7 Correct 28 ms 25228 KB Output is correct
8 Correct 23 ms 25228 KB Output is correct
9 Correct 25 ms 25228 KB Output is correct
10 Correct 22 ms 25228 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25228 KB Output is correct
2 Correct 22 ms 25228 KB Output is correct
3 Correct 23 ms 25228 KB Output is correct
4 Correct 23 ms 25228 KB Output is correct
5 Correct 22 ms 25228 KB Output is correct
6 Correct 22 ms 25228 KB Output is correct
7 Correct 22 ms 25228 KB Output is correct
8 Correct 21 ms 25276 KB Output is correct
9 Correct 23 ms 25276 KB Output is correct
10 Correct 23 ms 25276 KB Output is correct
11 Correct 27 ms 25276 KB Output is correct
12 Correct 22 ms 25276 KB Output is correct
13 Correct 27 ms 25276 KB Output is correct
14 Correct 26 ms 25276 KB Output is correct
15 Correct 39 ms 25276 KB Output is correct
16 Runtime error 121 ms 50716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -