oj.uz

Submission #1072445

# Submission time Handle Problem Language Result Execution time Memory
1072445 2024-08-23T19:14:55 Z Joshua_Andersson The Big Prize (IOI17_prize) C++14
20 / 100
 63 ms 1524 KB 
#include "prize.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

map<int, vi> cache;
vi q(int i)
{
	if (cache.find(i) != cache.end()) return cache[i];
	return cache[i] = ask(i);
}

int find_best(int n)
{
	int lollipop_cnt = 0;
	int i = 0;
	rep(i, 500)
	{
		vi res = q(i);
		int s = res[0] + res[1];
		if (s==0)
		{
			return i;
		}
		if (s*s*s*s>n)
		{
			lollipop_cnt = s;
			break;
		}
		lollipop_cnt = max(lollipop_cnt, s);
		i++;
	}
	
	int jump = 220;
	while (true)
	{
		vi base = q(i);
		if (base[0]+base[1]==0)
		{
			return i;
		}
		
		if (base[0]+base[1]==lollipop_cnt)
		{
			if (i+ jump <n)
			{
				vi b2 = q(i + jump);
				if (b2 == base)
				{
					i += jump;
					continue;
				}
			}
			
			int lo = i;
			int hi = min(n, i+ jump);
			while (lo+1<hi)
			{
				int mid = (lo + hi) / 2;
				vi m = q(mid);
				if (m == base)
				{
					lo = mid;
				}
				else hi = mid;
			}
			i = hi;
		}
		else
		{
			i++;
		}
	}

	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 6 ms 476 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 3 ms 452 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 4 ms 448 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 6 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 4 ms 344 KB Output is correct
16 Correct 14 ms 872 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Partially correct 26 ms 1160 KB Partially correct - number of queries: 5137
19 Correct 1 ms 344 KB Output is correct
20 Incorrect 63 ms 1524 KB Incorrect
21 Halted 0 ms 0 KB -