Submission #289171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
289171	2020-09-02T12:30:46 Z	Touubs	The Big Prize (IOI17_prize)	C++17	95.16 / 100	76 ms	5408 KB

prize

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

int non_worst_box_cnt = 0;


bool notworst(vector<int> res) {
    return (res[0] + res[1] != non_worst_box_cnt);
}

bool best(vector<int> res) {
    return (res[0] + res[1] == 0);
}

bool contains(int a, vector<int> ares, int b, vector<int> bres) {
    //cout << " checking between " << a << " and " << b << "\n";
    return bres[0] != ares[0];
}

vector<vector<int>> askcache(200000);
vector<bool> asked(200000);

vector<int> ask_(int i) {
    //cout << "asking " << i << "\n";
    if (!asked[i]) {
	asked[i] = true;
	askcache[i] = ask(i);
    }
    return askcache[i];
}

int binary_search(int min, int max) {
    if (min > max) return -1;
    if (min == max) {
	if (best(ask_(min))) return min;
	return -1;
    }
    int mid = (min + max) / 2;
    auto minres = ask_(min);
    if (notworst(minres)) {
	if (best(minres)) {
	    return min;
	}
	return binary_search(min + 1, max);
    }
    auto maxres = ask_(max);
    if (notworst(maxres)) {
	if (best(maxres)) {
	    return max;
	}
	return binary_search(min, max - 1);
    }
    auto midres = ask_(mid);
    if (notworst(midres)) {
	if (best(midres)) {
	    return mid;
	}
	if (min + 2 < max)
	return std::max(binary_search(min, mid), binary_search(mid, max));
	else
	return std::max(binary_search(min, mid), binary_search(mid + 1, max));

    }
    int opt = -1;
    if (contains(min, minres, mid, midres)) {
	opt = std::max(opt, binary_search(min, mid));
    }
    if (contains(mid, midres, max, maxres)) {
	if (min + 2 < max)
	opt = std::max(opt, binary_search(mid, max));
	else 
	opt = std::max(opt, binary_search(mid + 1, max));
    }
    return opt;
}

int find_best(int n) {

    for (int i = 0; i < 475 && i < n; i++) {
	auto v = ask_(i);
	int va = v[0];
	int vb = v[1];
	non_worst_box_cnt = max(non_worst_box_cnt, va + vb);
    }

    return binary_search(0, n - 1);

}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	5120 KB	Output is correct
2	Correct	10 ms	5120 KB	Output is correct
3	Correct	10 ms	5116 KB	Output is correct
4	Correct	8 ms	5248 KB	Output is correct
5	Correct	6 ms	5108 KB	Output is correct
6	Correct	8 ms	5120 KB	Output is correct
7	Correct	8 ms	5116 KB	Output is correct
8	Correct	10 ms	5120 KB	Output is correct
9	Correct	8 ms	5120 KB	Output is correct
10	Correct	8 ms	5120 KB	Output is correct

Subtask #2

75.16 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	5112 KB	Output is correct
2	Correct	8 ms	4992 KB	Output is correct
3	Correct	8 ms	5120 KB	Output is correct
4	Correct	8 ms	4992 KB	Output is correct
5	Correct	8 ms	4992 KB	Output is correct
6	Correct	8 ms	5096 KB	Output is correct
7	Correct	10 ms	5112 KB	Output is correct
8	Correct	7 ms	5112 KB	Output is correct
9	Correct	8 ms	5112 KB	Output is correct
10	Correct	7 ms	5120 KB	Output is correct
11	Correct	13 ms	5112 KB	Output is correct
12	Correct	11 ms	5120 KB	Output is correct
13	Correct	9 ms	5116 KB	Output is correct
14	Correct	22 ms	5120 KB	Output is correct
15	Partially correct	66 ms	5240 KB	Partially correct - number of queries: 5164
16	Partially correct	61 ms	5240 KB	Partially correct - number of queries: 5423
17	Partially correct	36 ms	5284 KB	Partially correct - number of queries: 5387
18	Partially correct	53 ms	5240 KB	Partially correct - number of queries: 5376
19	Partially correct	32 ms	5272 KB	Partially correct - number of queries: 5088
20	Correct	36 ms	5120 KB	Output is correct
21	Partially correct	63 ms	5276 KB	Partially correct - number of queries: 5389
22	Correct	42 ms	5120 KB	Output is correct
23	Correct	9 ms	5112 KB	Output is correct
24	Correct	16 ms	5120 KB	Output is correct
25	Partially correct	35 ms	5252 KB	Partially correct - number of queries: 5023
26	Correct	69 ms	5240 KB	Output is correct
27	Correct	11 ms	5112 KB	Output is correct
28	Correct	69 ms	5240 KB	Output is correct
29	Correct	58 ms	5112 KB	Output is correct
30	Partially correct	63 ms	5240 KB	Partially correct - number of queries: 5350
31	Partially correct	48 ms	5240 KB	Partially correct - number of queries: 5351
32	Correct	16 ms	5112 KB	Output is correct
33	Correct	4 ms	5108 KB	Output is correct
34	Partially correct	36 ms	5272 KB	Partially correct - number of queries: 5385
35	Correct	12 ms	5120 KB	Output is correct
36	Partially correct	74 ms	5240 KB	Partially correct - number of queries: 5343
37	Correct	15 ms	5120 KB	Output is correct
38	Correct	11 ms	5112 KB	Output is correct
39	Partially correct	73 ms	5224 KB	Partially correct - number of queries: 5348
40	Correct	66 ms	5240 KB	Output is correct
41	Partially correct	52 ms	5176 KB	Partially correct - number of queries: 5395
42	Partially correct	70 ms	5244 KB	Partially correct - number of queries: 5395
43	Partially correct	45 ms	5240 KB	Partially correct - number of queries: 5271
44	Partially correct	39 ms	5252 KB	Partially correct - number of queries: 5401
45	Partially correct	54 ms	5240 KB	Partially correct - number of queries: 5019
46	Partially correct	73 ms	5240 KB	Partially correct - number of queries: 5379
47	Partially correct	69 ms	5240 KB	Partially correct - number of queries: 5035
48	Partially correct	71 ms	5240 KB	Partially correct - number of queries: 5364
49	Partially correct	72 ms	5240 KB	Partially correct - number of queries: 5366
50	Partially correct	48 ms	5228 KB	Partially correct - number of queries: 5399
51	Partially correct	76 ms	5240 KB	Partially correct - number of queries: 5407
52	Partially correct	69 ms	5240 KB	Partially correct - number of queries: 5422
53	Correct	10 ms	5120 KB	Output is correct
54	Partially correct	55 ms	5240 KB	Partially correct - number of queries: 5364
55	Partially correct	69 ms	5240 KB	Partially correct - number of queries: 5400
56	Partially correct	34 ms	5408 KB	Partially correct - number of queries: 5365
57	Partially correct	50 ms	5240 KB	Partially correct - number of queries: 5376
58	Partially correct	48 ms	5240 KB	Partially correct - number of queries: 5375
59	Partially correct	69 ms	5356 KB	Partially correct - number of queries: 5382
60	Partially correct	58 ms	5240 KB	Partially correct - number of queries: 5349
61	Correct	12 ms	5248 KB	Output is correct
62	Correct	12 ms	5112 KB	Output is correct
63	Correct	10 ms	5112 KB	Output is correct
64	Correct	11 ms	5120 KB	Output is correct
65	Correct	8 ms	5112 KB	Output is correct
66	Correct	7 ms	5120 KB	Output is correct
67	Correct	12 ms	5120 KB	Output is correct
68	Correct	8 ms	5120 KB	Output is correct
69	Correct	9 ms	5112 KB	Output is correct
70	Correct	8 ms	5144 KB	Output is correct
71	Partially correct	48 ms	5240 KB	Partially correct - number of queries: 5234
72	Correct	15 ms	5120 KB	Output is correct
73	Partially correct	56 ms	5240 KB	Partially correct - number of queries: 5171
74	Partially correct	52 ms	5240 KB	Partially correct - number of queries: 5198
75	Correct	8 ms	5248 KB	Output is correct
76	Correct	43 ms	5240 KB	Output is correct
77	Partially correct	54 ms	5240 KB	Partially correct - number of queries: 5484
78	Correct	12 ms	5120 KB	Output is correct
79	Correct	31 ms	5248 KB	Output is correct
80	Partially correct	61 ms	5240 KB	Partially correct - number of queries: 5476
81	Partially correct	59 ms	5240 KB	Partially correct - number of queries: 5468
82	Partially correct	55 ms	5368 KB	Partially correct - number of queries: 5453
83	Correct	11 ms	5120 KB	Output is correct
84	Correct	48 ms	5240 KB	Output is correct
85	Partially correct	52 ms	5240 KB	Partially correct - number of queries: 5484
86	Correct	8 ms	5120 KB	Output is correct
87	Correct	8 ms	5120 KB	Output is correct
88	Correct	9 ms	5120 KB	Output is correct
89	Correct	9 ms	5120 KB	Output is correct
90	Correct	8 ms	4992 KB	Output is correct
91	Correct	8 ms	5120 KB	Output is correct
92	Correct	8 ms	5120 KB	Output is correct
93	Correct	12 ms	5120 KB	Output is correct
94	Correct	11 ms	5120 KB	Output is correct
95	Correct	13 ms	5248 KB	Output is correct
96	Correct	11 ms	5120 KB	Output is correct
97	Correct	8 ms	5120 KB	Output is correct