답안 #33911 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33911	2017-11-05T01:16:35 Z	imeimi2000	커다란 상품 (IOI17_prize)	C++14	100 / 100	33 ms	3724 KB

prize

#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;
        ^

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	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

Subtask #2
80.0 / 80.0

#	결과	실행 시간	메모리	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

답안 #33911

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 80.0 / 80.0

Subtask #1
20.0 / 20.0

Subtask #2
80.0 / 80.0