Submission #1072452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1072452	2024-08-23T19:21:45 Z	Joshua_Andersson	The Big Prize (IOI17_prize)	C++14	20 / 100	29 ms	1252 KB

prize

#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, 450)
	{
		vi res = q(i);
		ll s = res[0] + res[1];
		if (s==0)
		{
			return i;
		}
		// assume that i is second most common
		// then there are s^2 of type t[i], and s^4 of most common type
		/*if (s*s*s*s>n)
		{
			lollipop_cnt = s;
			break;
		}*/
		lollipop_cnt = max(lollipop_cnt, (int)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	2 ms	344 KB	Output is correct
2	Correct	4 ms	344 KB	Output is correct
3	Correct	5 ms	428 KB	Output is correct
4	Correct	7 ms	500 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	4 ms	344 KB	Output is correct
9	Correct	3 ms	344 KB	Output is correct
10	Correct	7 ms	344 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Correct	6 ms	344 KB	Output is correct
3	Correct	2 ms	344 KB	Output is correct
4	Correct	6 ms	344 KB	Output is correct
5	Correct	3 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	5 ms	344 KB	Output is correct
8	Correct	3 ms	344 KB	Output is correct
9	Correct	3 ms	344 KB	Output is correct
10	Correct	4 ms	600 KB	Output is correct
11	Correct	3 ms	600 KB	Output is correct
12	Correct	2 ms	620 KB	Output is correct
13	Correct	8 ms	600 KB	Output is correct
14	Correct	3 ms	344 KB	Output is correct
15	Correct	5 ms	428 KB	Output is correct
16	Correct	20 ms	848 KB	Output is correct
17	Correct	2 ms	344 KB	Output is correct
18	Partially correct	29 ms	848 KB	Partially correct - number of queries: 5112
19	Correct	2 ms	456 KB	Output is correct
20	Correct	7 ms	344 KB	Output is correct
21	Correct	13 ms	740 KB	Output is correct
22	Correct	3 ms	724 KB	Output is correct
23	Correct	2 ms	344 KB	Output is correct
24	Correct	1 ms	344 KB	Output is correct
25	Correct	15 ms	856 KB	Output is correct
26	Correct	17 ms	540 KB	Output is correct
27	Correct	3 ms	344 KB	Output is correct
28	Partially correct	25 ms	848 KB	Partially correct - number of queries: 5045
29	Correct	15 ms	848 KB	Output is correct
30	Correct	21 ms	1252 KB	Output is correct
31	Correct	1 ms	344 KB	Output is correct
32	Correct	6 ms	344 KB	Output is correct
33	Incorrect	1 ms	344 KB	Integer 100 violates the range [0, 99]
34	Halted	0 ms	0 KB	-