oj.uz

Submission #54223

# Submission time Handle Problem Language Result Execution time Memory
54223 2018-07-02T21:01:07 Z radoslav11 The Big Prize (IOI17_prize) C++14
20 / 100
 98 ms 25408 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 = i + 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 22 ms 24824 KB Output is correct
2 Correct 25 ms 25040 KB Output is correct
3 Correct 26 ms 25040 KB Output is correct
4 Correct 25 ms 25040 KB Output is correct
5 Correct 22 ms 25084 KB Output is correct
6 Correct 21 ms 25084 KB Output is correct
7 Correct 23 ms 25120 KB Output is correct
8 Correct 22 ms 25124 KB Output is correct
9 Correct 22 ms 25252 KB Output is correct
10 Correct 21 ms 25252 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25252 KB Output is correct
2 Correct 22 ms 25252 KB Output is correct
3 Correct 22 ms 25252 KB Output is correct
4 Correct 23 ms 25276 KB Output is correct
5 Correct 23 ms 25276 KB Output is correct
6 Correct 22 ms 25276 KB Output is correct
7 Correct 22 ms 25276 KB Output is correct
8 Correct 22 ms 25276 KB Output is correct
9 Correct 22 ms 25276 KB Output is correct
10 Correct 22 ms 25276 KB Output is correct
11 Correct 25 ms 25276 KB Output is correct
12 Correct 21 ms 25276 KB Output is correct
13 Correct 28 ms 25276 KB Output is correct
14 Correct 24 ms 25276 KB Output is correct
15 Correct 39 ms 25276 KB Output is correct
16 Incorrect 98 ms 25408 KB Incorrect
17 Halted 0 ms 0 KB -