답안 #52169 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52169	2018-06-24T12:34:04 Z	ernestvw	커다란 상품 (IOI17_prize)	C++11	97.55 / 100	91 ms	11580 KB

prize

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

#include "prize.h"
//vector<int> ask(int i);

vector<int> series;

int N;

vector<int> memo[200001];
vector<int> query(int i) {
	if(i == -42) return {2*N, 2*N};
	if(i < 0 or i > N-1)
		return {0, 0};
	if(memo[i][0] != -1) return memo[i];
	else return memo[i] = ask(i);
}

/*int find(int l, int r) {
	if(l == r) return l;
	int mid = (l+r)/2;
	vector<int> q = query(mid);
	if(q[0] == 0 and q[1] == 0) return mid;
	else if(q[0] == 0) return find(mid+1, r);
	return find(l, mid-1);
}*/

bool bigger(int i, int j) {
	vector<int> q1 = query(i);
	vector<int> q2 = query(j);
	return q1[0] + q1[1] < q2[0] + q2[1];
}

int MINI = -1;

bool ok(int i) {
	vector<int> q = query(i);
	return MINI == q[0] + q[1];
}

int L(int i) {
	vector<int> q = query(i);
	return q[0];
}

int R(int i) {
	vector<int> q = query(i);
	return q[1];
}

int S(int i) {
	vector<int> q = query(i);
	return q[0] + q[1];
}

int find(int l, int r) {
	if(l > r or l < 0 or r > N-1) return -42;
	if(l == r) return l;
	int rB = R(r+1);
	int lB = L(l-1);
	int mid = (l + r) / 2;
	vector<int> q = query(mid);
	vector<int> candidates = {mid};
	if(R(mid) - rB != 0) candidates.push_back(find(mid+1, r));
	if(L(mid) - lB != 0) candidates.push_back(find(l, mid-1));
	int ans = -1;
	int mini = N+1;
	for(int i : candidates) if(S(i) < mini) mini = S(i), ans = i;
	return ans;
}

int solve() {
	/*if(N <= 5000) {
		for(int i = 0; i < N; i++) {
			vector<int> q = query(i);
			if(q[0] + q[1] == 0) return i;
		}
	}*/
	return find(0, N-1);
}

int find_best(int n) {
	series.clear();
	long long cur = 1;
	series.push_back(cur);
	while(cur * cur + 1LL < (long long)n) {
		series.push_back(cur * cur + 1LL);
		cur = cur * cur + 1LL;
	}
	N = n;
	for(int i = 0; i < N; i++) memo[i] = {-1, -1};
	//return find(0, N-1);
	return solve();
}

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	11256 KB	Output is correct
2	Correct	25 ms	11316 KB	Output is correct
3	Correct	20 ms	11316 KB	Output is correct
4	Correct	31 ms	11316 KB	Output is correct
5	Correct	19 ms	11324 KB	Output is correct
6	Correct	19 ms	11452 KB	Output is correct
7	Correct	24 ms	11452 KB	Output is correct
8	Correct	25 ms	11456 KB	Output is correct
9	Correct	19 ms	11456 KB	Output is correct
10	Correct	31 ms	11456 KB	Output is correct

Subtask #2
77.55 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	11456 KB	Output is correct
2	Correct	23 ms	11456 KB	Output is correct
3	Correct	22 ms	11456 KB	Output is correct
4	Correct	20 ms	11456 KB	Output is correct
5	Correct	18 ms	11456 KB	Output is correct
6	Correct	19 ms	11456 KB	Output is correct
7	Correct	24 ms	11456 KB	Output is correct
8	Correct	19 ms	11456 KB	Output is correct
9	Correct	18 ms	11528 KB	Output is correct
10	Correct	19 ms	11528 KB	Output is correct
11	Correct	26 ms	11528 KB	Output is correct
12	Correct	23 ms	11528 KB	Output is correct
13	Correct	26 ms	11528 KB	Output is correct
14	Correct	16 ms	11528 KB	Output is correct
15	Correct	62 ms	11528 KB	Output is correct
16	Partially correct	69 ms	11528 KB	Partially correct - number of queries: 5041
17	Partially correct	84 ms	11528 KB	Partially correct - number of queries: 5074
18	Partially correct	48 ms	11528 KB	Partially correct - number of queries: 5065
19	Correct	72 ms	11528 KB	Output is correct
20	Correct	27 ms	11528 KB	Output is correct
21	Partially correct	76 ms	11528 KB	Partially correct - number of queries: 5009
22	Correct	56 ms	11580 KB	Output is correct
23	Correct	23 ms	11580 KB	Output is correct
24	Correct	24 ms	11580 KB	Output is correct
25	Correct	53 ms	11580 KB	Output is correct
26	Correct	80 ms	11580 KB	Output is correct
27	Correct	25 ms	11580 KB	Output is correct
28	Correct	61 ms	11580 KB	Output is correct
29	Correct	53 ms	11580 KB	Output is correct
30	Partially correct	68 ms	11580 KB	Partially correct - number of queries: 5025
31	Partially correct	71 ms	11580 KB	Partially correct - number of queries: 5021
32	Correct	23 ms	11580 KB	Output is correct
33	Correct	6 ms	11580 KB	Output is correct
34	Partially correct	85 ms	11580 KB	Partially correct - number of queries: 5049
35	Correct	25 ms	11580 KB	Output is correct
36	Partially correct	81 ms	11580 KB	Partially correct - number of queries: 5058
37	Correct	24 ms	11580 KB	Output is correct
38	Correct	28 ms	11580 KB	Output is correct
39	Partially correct	58 ms	11580 KB	Partially correct - number of queries: 5068
40	Correct	55 ms	11580 KB	Output is correct
41	Partially correct	67 ms	11580 KB	Partially correct - number of queries: 5094
42	Partially correct	77 ms	11580 KB	Partially correct - number of queries: 5094
43	Correct	75 ms	11580 KB	Output is correct
44	Partially correct	62 ms	11580 KB	Partially correct - number of queries: 5053
45	Correct	61 ms	11580 KB	Output is correct
46	Partially correct	54 ms	11580 KB	Partially correct - number of queries: 5062
47	Correct	61 ms	11580 KB	Output is correct
48	Partially correct	68 ms	11580 KB	Partially correct - number of queries: 5081
49	Partially correct	49 ms	11580 KB	Partially correct - number of queries: 5085
50	Partially correct	68 ms	11580 KB	Partially correct - number of queries: 5071
51	Partially correct	58 ms	11580 KB	Partially correct - number of queries: 5074
52	Partially correct	70 ms	11580 KB	Partially correct - number of queries: 5066
53	Correct	20 ms	11580 KB	Output is correct
54	Partially correct	57 ms	11580 KB	Partially correct - number of queries: 5014
55	Partially correct	54 ms	11580 KB	Partially correct - number of queries: 5065
56	Partially correct	75 ms	11580 KB	Partially correct - number of queries: 5058
57	Partially correct	84 ms	11580 KB	Partially correct - number of queries: 5021
58	Partially correct	67 ms	11580 KB	Partially correct - number of queries: 5086
59	Partially correct	91 ms	11580 KB	Partially correct - number of queries: 5092
60	Partially correct	54 ms	11580 KB	Partially correct - number of queries: 5035
61	Correct	21 ms	11580 KB	Output is correct
62	Correct	23 ms	11580 KB	Output is correct
63	Correct	20 ms	11580 KB	Output is correct
64	Correct	21 ms	11580 KB	Output is correct
65	Correct	23 ms	11580 KB	Output is correct
66	Correct	26 ms	11580 KB	Output is correct
67	Correct	21 ms	11580 KB	Output is correct
68	Correct	19 ms	11580 KB	Output is correct
69	Correct	21 ms	11580 KB	Output is correct
70	Correct	19 ms	11580 KB	Output is correct
71	Correct	66 ms	11580 KB	Output is correct
72	Correct	26 ms	11580 KB	Output is correct
73	Correct	71 ms	11580 KB	Output is correct
74	Correct	45 ms	11580 KB	Output is correct
75	Correct	24 ms	11580 KB	Output is correct
76	Correct	54 ms	11580 KB	Output is correct
77	Partially correct	72 ms	11580 KB	Partially correct - number of queries: 5230
78	Correct	23 ms	11580 KB	Output is correct
79	Correct	39 ms	11580 KB	Output is correct
80	Partially correct	69 ms	11580 KB	Partially correct - number of queries: 5231
81	Partially correct	69 ms	11580 KB	Partially correct - number of queries: 5176
82	Partially correct	65 ms	11580 KB	Partially correct - number of queries: 5178
83	Correct	21 ms	11580 KB	Output is correct
84	Correct	58 ms	11580 KB	Output is correct
85	Partially correct	63 ms	11580 KB	Partially correct - number of queries: 5245
86	Correct	37 ms	11580 KB	Output is correct
87	Correct	22 ms	11580 KB	Output is correct
88	Correct	25 ms	11580 KB	Output is correct
89	Correct	24 ms	11580 KB	Output is correct
90	Correct	20 ms	11580 KB	Output is correct
91	Correct	23 ms	11580 KB	Output is correct
92	Correct	18 ms	11580 KB	Output is correct
93	Correct	29 ms	11580 KB	Output is correct
94	Correct	21 ms	11580 KB	Output is correct
95	Correct	23 ms	11580 KB	Output is correct
96	Correct	22 ms	11580 KB	Output is correct
97	Correct	18 ms	11580 KB	Output is correct

답안 #52169

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 77.55 / 80.0

Subtask #1
20.0 / 20.0

Subtask #2
77.55 / 80.0