Submission #43145

# Submission time Handle Problem Language Result Execution time Memory
43145 2018-03-09T10:33:43 Z RayaBurong25_1 The Big Prize (IOI17_prize) C++14
94.3 / 100
18 ms 4364 KB
#include "prize.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
int L[200005], R[200005];
int V[200005];
int min(int a, int b)
{
	return (a < b)?a:b;
}
int max(int a, int b)
{
	return (a > b)?a:b;
}
int find_best(int n) {
	int i, j;
	for (i = 0; i < n; i++)
		L[i] = -1;
	int mn, md, mx;
	//first sig
	std::vector<int> r;
	r = ask(0);
	L[0] = r[0];
	R[0] = r[1];
	if (R[0] == 0)
		return 0;
	r = ask(n - 1);
	L[n - 1] = r[0];
	R[n - 1] = r[1];
	if (L[n - 1] == 0)
		return n - 1;
	int sigl = 0, sigr = n - 1;
	while (sigl < sigr)
	{
		for (i = 0; i < 2; i++)
		{
			for (j = sigr; j > sigl; j--)
				if (L[j] != -1 && L[j] != L[sigr] && R[j] != R[sigr])
					break;
		mn = j;
		mx = sigr;
		while (mx != mn)
		{
			if (mx - mn == 1)
			{
				sigr = mn;
				break;
			}
			md = (mn + mx)/2;
			if (L[md] == -1)
			{
				r = ask(md);
				L[md] = r[0];
				R[md] = r[1];
			}
			if (L[md] == 0 && R[md] == 0)
				return md;
			if (L[md] == L[sigr] && R[md] == R[sigr])
				mx = md;
			else
				mn = md;
		}
		if (L[sigr] == -1)
		{
			r = ask(sigr);
			L[sigr] = r[0];
			R[sigr] = r[1];
		}
		if (L[sigr] == 0 && R[sigr] == 0)
			return sigr;
		}
		// printf("sigl %d sigr %d\n", sigl, sigr);
		for (i = 0; i < 2; i++)
		{
			for (j = sigl; j < sigr; j++)
				if (L[j] != -1 && L[j] != L[sigr] && R[j] != R[sigr])
					break;
		mn = sigl;
		mx = j;
		while (mx != mn)
		{
			if (mx - mn == 1)
			{
				sigl = mx;
				break;
			}
			md = (mn + mx)/2;
			if (L[md] == -1)
			{
				r = ask(md);
				L[md] = r[0];
				R[md] = r[1];
			}
			if (L[md] == 0 && R[md] == 0)
				return md;
			if (L[md] == L[sigl] && R[md] == R[sigl])
				mn = md;
			else
				mx = md;
		}
		if (L[sigl] == -1)
		{
			r = ask(sigl);
			L[sigl] = r[0];
			R[sigl] = r[1];
		}
		if (L[sigl] == 0 && R[sigl] == 0)
			return sigl;
		}
	}
	if (sigl == sigr)
		return sigl;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 4364 KB Output is correct
2 Correct 1 ms 4364 KB Output is correct
3 Correct 1 ms 4364 KB Output is correct
4 Correct 1 ms 4364 KB Output is correct
5 Correct 0 ms 4364 KB Output is correct
6 Correct 1 ms 4364 KB Output is correct
7 Correct 1 ms 4364 KB Output is correct
8 Correct 2 ms 4364 KB Output is correct
9 Correct 1 ms 4364 KB Output is correct
10 Correct 1 ms 4364 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 4364 KB Output is correct
2 Correct 0 ms 4364 KB Output is correct
3 Correct 1 ms 4364 KB Output is correct
4 Correct 0 ms 4364 KB Output is correct
5 Correct 0 ms 4364 KB Output is correct
6 Correct 1 ms 4364 KB Output is correct
7 Correct 1 ms 4364 KB Output is correct
8 Correct 1 ms 4364 KB Output is correct
9 Correct 1 ms 4364 KB Output is correct
10 Correct 0 ms 4364 KB Output is correct
11 Correct 5 ms 4364 KB Output is correct
12 Correct 3 ms 4364 KB Output is correct
13 Correct 1 ms 4364 KB Output is correct
14 Correct 0 ms 4364 KB Output is correct
15 Correct 7 ms 4364 KB Output is correct
16 Correct 11 ms 4364 KB Output is correct
17 Partially correct 15 ms 4364 KB Partially correct - number of queries: 5309
18 Correct 1 ms 4364 KB Output is correct
19 Correct 9 ms 4364 KB Output is correct
20 Correct 1 ms 4364 KB Output is correct
21 Correct 2 ms 4364 KB Output is correct
22 Correct 5 ms 4364 KB Output is correct
23 Correct 0 ms 4364 KB Output is correct
24 Correct 4 ms 4364 KB Output is correct
25 Correct 0 ms 4364 KB Output is correct
26 Correct 6 ms 4364 KB Output is correct
27 Correct 2 ms 4364 KB Output is correct
28 Correct 3 ms 4364 KB Output is correct
29 Correct 0 ms 4364 KB Output is correct
30 Correct 0 ms 4364 KB Output is correct
31 Partially correct 15 ms 4364 KB Partially correct - number of queries: 5249
32 Correct 5 ms 4364 KB Output is correct
33 Correct 0 ms 4364 KB Output is correct
34 Correct 15 ms 4364 KB Output is correct
35 Correct 2 ms 4364 KB Output is correct
36 Correct 13 ms 4364 KB Output is correct
37 Correct 6 ms 4364 KB Output is correct
38 Correct 2 ms 4364 KB Output is correct
39 Correct 13 ms 4364 KB Output is correct
40 Correct 1 ms 4364 KB Output is correct
41 Correct 6 ms 4364 KB Output is correct
42 Correct 8 ms 4364 KB Output is correct
43 Correct 1 ms 4364 KB Output is correct
44 Correct 17 ms 4364 KB Output is correct
45 Correct 11 ms 4364 KB Output is correct
46 Partially correct 0 ms 4364 KB Partially correct - number of queries: 5279
47 Correct 5 ms 4364 KB Output is correct
48 Correct 1 ms 4364 KB Output is correct
49 Correct 3 ms 4364 KB Output is correct
50 Correct 1 ms 4364 KB Output is correct
51 Correct 4 ms 4364 KB Output is correct
52 Partially correct 14 ms 4364 KB Partially correct - number of queries: 5237
53 Correct 0 ms 4364 KB Output is correct
54 Correct 15 ms 4364 KB Output is correct
55 Partially correct 10 ms 4364 KB Partially correct - number of queries: 5053
56 Correct 1 ms 4364 KB Output is correct
57 Correct 9 ms 4364 KB Output is correct
58 Correct 3 ms 4364 KB Output is correct
59 Correct 16 ms 4364 KB Output is correct
60 Correct 1 ms 4364 KB Output is correct
61 Correct 1 ms 4364 KB Output is correct
62 Correct 1 ms 4364 KB Output is correct
63 Correct 1 ms 4364 KB Output is correct
64 Correct 2 ms 4364 KB Output is correct
65 Correct 1 ms 4364 KB Output is correct
66 Correct 1 ms 4364 KB Output is correct
67 Correct 1 ms 4364 KB Output is correct
68 Correct 1 ms 4364 KB Output is correct
69 Correct 1 ms 4364 KB Output is correct
70 Correct 1 ms 4364 KB Output is correct
71 Partially correct 7 ms 4364 KB Partially correct - number of queries: 5169
72 Correct 5 ms 4364 KB Output is correct
73 Partially correct 18 ms 4364 KB Partially correct - number of queries: 5095
74 Partially correct 13 ms 4364 KB Partially correct - number of queries: 5120
75 Correct 3 ms 4364 KB Output is correct
76 Correct 9 ms 4364 KB Output is correct
77 Partially correct 9 ms 4364 KB Partially correct - number of queries: 5493
78 Correct 5 ms 4364 KB Output is correct
79 Correct 8 ms 4364 KB Output is correct
80 Partially correct 8 ms 4364 KB Partially correct - number of queries: 5570
81 Partially correct 5 ms 4364 KB Partially correct - number of queries: 5480
82 Partially correct 8 ms 4364 KB Partially correct - number of queries: 5468
83 Correct 1 ms 4364 KB Output is correct
84 Correct 13 ms 4364 KB Output is correct
85 Partially correct 17 ms 4364 KB Partially correct - number of queries: 5535
86 Correct 5 ms 4364 KB Output is correct
87 Correct 9 ms 4364 KB Output is correct
88 Correct 5 ms 4364 KB Output is correct
89 Correct 3 ms 4364 KB Output is correct
90 Correct 2 ms 4364 KB Output is correct
91 Correct 2 ms 4364 KB Output is correct
92 Correct 1 ms 4364 KB Output is correct
93 Correct 1 ms 4364 KB Output is correct
94 Correct 2 ms 4364 KB Output is correct
95 Correct 1 ms 4364 KB Output is correct
96 Correct 0 ms 4364 KB Output is correct
97 Correct 1 ms 4364 KB Output is correct