Submission #33911

# Submission time Handle Problem Language Result Execution time Memory
33911 2017-11-05T01:16:35 Z imeimi2000 The Big Prize (IOI17_prize) C++14
100 / 100
33 ms 3724 KB
#include "prize.h"
#include <algorithm>

using namespace std;
typedef pair<int, int> pi;

//1 + 4 + 21 + 446 = 472
const int MAXDIA = 473;
int n, m, g, r;

pi save[200000];
pi question(int i) {
	if (save[i] != pi(0, 0)) return save[i];
	vector<int> ret = ask(i);
	if (ret[0] == 0 && ret[1] == 0) throw i;
	return save[i] = pi(ret[0], ret[1]);
}

void bsearch(int s, int e, int lc, int rc, int c) {
	if (c == 0) return;
	if (c == e - s + 1) {
		for (int i = s; i <= e; ++i) question(i);
		return;
	}
	int md = (s + e) / 2;
	int l = md + 1, r = md, p;
	for (int i = 0; i <= e - s; ++i) {
		if (i % 2 == 0) p = --l;
		else p = ++r;
		pi ret = question(p);
		int ls = ret.first - lc - (i % 2 == 0 ? 0 : r - l);
		if (ret.first + ret.second == m) {
			bsearch(s, l - 1, lc, rc + c - ls, ls);
			bsearch(r + 1, e, lc + ls + r - l, rc, c - ls - r + l);
			break;
		}
	}
}

int find_best(int N) {
	n = N;
	if (n < MAXDIA) {
		for (int i = 0; i < n; ++i) {
			vector<int> ret = ask(i);
			if (ret[0] == 0 && ret[1] == 0) return i;
		}
	}
	g = n / MAXDIA;
	r = n - MAXDIA * g;

	try {
		int i, s, e;
		for (i = 0, s = 0; i < MAXDIA; ++i) {
			if (i < r) e = s + g;
			else e = s + g - 1;
			pi ret = question(e);
			m = max(m, ret.first + ret.second);
			s = e + 1;
		}
		int lc = 0;
		for (i = 0, s = 0; i < MAXDIA; ++i) {
			if (i < r) e = s + g;
			else e = s + g - 1;
			pi ret = question(e);
			int j = e;
			int ct = 0;
			while (s < j && ret.first + ret.second != m) {
				ret = question(--j);
			}
			bsearch(s, j - 1, lc, ret.second, ret.first - lc);
			lc = e - j + ret.first;
			s = e + 1;
		}
	}
	catch (int i) {
		return i;
	}

	return 0;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:66:8: warning: unused variable 'ct' [-Wunused-variable]
    int ct = 0;
        ^
# Verdict Execution time Memory Grader output
1 Correct 6 ms 3724 KB Output is correct
2 Correct 0 ms 3724 KB Output is correct
3 Correct 3 ms 3724 KB Output is correct
4 Correct 3 ms 3724 KB Output is correct
5 Correct 3 ms 3724 KB Output is correct
6 Correct 0 ms 3724 KB Output is correct
7 Correct 3 ms 3724 KB Output is correct
8 Correct 6 ms 3724 KB Output is correct
9 Correct 0 ms 3724 KB Output is correct
10 Correct 3 ms 3724 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 3724 KB Output is correct
2 Correct 0 ms 3724 KB Output is correct
3 Correct 3 ms 3724 KB Output is correct
4 Correct 3 ms 3724 KB Output is correct
5 Correct 3 ms 3724 KB Output is correct
6 Correct 3 ms 3724 KB Output is correct
7 Correct 6 ms 3724 KB Output is correct
8 Correct 6 ms 3724 KB Output is correct
9 Correct 0 ms 3724 KB Output is correct
10 Correct 0 ms 3724 KB Output is correct
11 Correct 0 ms 3724 KB Output is correct
12 Correct 13 ms 3724 KB Output is correct
13 Correct 9 ms 3724 KB Output is correct
14 Correct 9 ms 3724 KB Output is correct
15 Correct 3 ms 3724 KB Output is correct
16 Correct 16 ms 3724 KB Output is correct
17 Correct 0 ms 3724 KB Output is correct
18 Correct 29 ms 3724 KB Output is correct
19 Correct 6 ms 3724 KB Output is correct
20 Correct 9 ms 3724 KB Output is correct
21 Correct 9 ms 3724 KB Output is correct
22 Correct 9 ms 3724 KB Output is correct
23 Correct 0 ms 3724 KB Output is correct
24 Correct 0 ms 3724 KB Output is correct
25 Correct 6 ms 3724 KB Output is correct
26 Correct 6 ms 3724 KB Output is correct
27 Correct 3 ms 3724 KB Output is correct
28 Correct 19 ms 3724 KB Output is correct
29 Correct 3 ms 3724 KB Output is correct
30 Correct 3 ms 3724 KB Output is correct
31 Correct 0 ms 3724 KB Output is correct
32 Correct 13 ms 3724 KB Output is correct
33 Correct 0 ms 3580 KB Output is correct
34 Correct 6 ms 3724 KB Output is correct
35 Correct 0 ms 3724 KB Output is correct
36 Correct 0 ms 3724 KB Output is correct
37 Correct 3 ms 3724 KB Output is correct
38 Correct 6 ms 3724 KB Output is correct
39 Correct 16 ms 3724 KB Output is correct
40 Correct 0 ms 3724 KB Output is correct
41 Correct 6 ms 3724 KB Output is correct
42 Correct 3 ms 3724 KB Output is correct
43 Correct 0 ms 3724 KB Output is correct
44 Correct 6 ms 3724 KB Output is correct
45 Correct 3 ms 3724 KB Output is correct
46 Correct 0 ms 3724 KB Output is correct
47 Correct 6 ms 3724 KB Output is correct
48 Correct 13 ms 3724 KB Output is correct
49 Correct 6 ms 3724 KB Output is correct
50 Correct 16 ms 3724 KB Output is correct
51 Correct 13 ms 3724 KB Output is correct
52 Correct 6 ms 3724 KB Output is correct
53 Correct 6 ms 3724 KB Output is correct
54 Correct 16 ms 3724 KB Output is correct
55 Correct 3 ms 3724 KB Output is correct
56 Correct 6 ms 3724 KB Output is correct
57 Correct 16 ms 3724 KB Output is correct
58 Correct 16 ms 3724 KB Output is correct
59 Correct 3 ms 3724 KB Output is correct
60 Correct 9 ms 3724 KB Output is correct
61 Correct 0 ms 3724 KB Output is correct
62 Correct 6 ms 3724 KB Output is correct
63 Correct 3 ms 3724 KB Output is correct
64 Correct 6 ms 3724 KB Output is correct
65 Correct 9 ms 3724 KB Output is correct
66 Correct 9 ms 3724 KB Output is correct
67 Correct 9 ms 3724 KB Output is correct
68 Correct 13 ms 3724 KB Output is correct
69 Correct 3 ms 3724 KB Output is correct
70 Correct 3 ms 3724 KB Output is correct
71 Correct 29 ms 3724 KB Output is correct
72 Correct 3 ms 3724 KB Output is correct
73 Correct 6 ms 3724 KB Output is correct
74 Correct 16 ms 3724 KB Output is correct
75 Correct 6 ms 3724 KB Output is correct
76 Correct 13 ms 3724 KB Output is correct
77 Correct 16 ms 3724 KB Output is correct
78 Correct 3 ms 3724 KB Output is correct
79 Correct 13 ms 3724 KB Output is correct
80 Correct 33 ms 3724 KB Output is correct
81 Correct 6 ms 3724 KB Output is correct
82 Correct 13 ms 3724 KB Output is correct
83 Correct 6 ms 3724 KB Output is correct
84 Correct 13 ms 3724 KB Output is correct
85 Correct 6 ms 3724 KB Output is correct
86 Correct 6 ms 3724 KB Output is correct
87 Correct 3 ms 3724 KB Output is correct
88 Correct 9 ms 3724 KB Output is correct
89 Correct 0 ms 3724 KB Output is correct
90 Correct 0 ms 3724 KB Output is correct
91 Correct 0 ms 3724 KB Output is correct
92 Correct 3 ms 3724 KB Output is correct
93 Correct 6 ms 3724 KB Output is correct
94 Correct 6 ms 3724 KB Output is correct
95 Correct 6 ms 3724 KB Output is correct
96 Correct 6 ms 3724 KB Output is correct
97 Correct 6 ms 3724 KB Output is correct