oj.uz

Submission #1043016

# Submission time Handle Problem Language Result Execution time Memory
1043016 2024-08-03T17:47:46 Z Mr_Husanboy The Big Prize (IOI17_prize) C++17
20 / 100
 36 ms 436 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()

template<typename T>
int len(T &a){
	return a.size();
}
int _q = 0;

int find_best(int n) {
	if(n <= 5000){
		for(int i = 0; i < n; i ++){
			if(ask(i) == vector<int>{0, 0}){
				return i;
			}
		}
	}
	int j = 0;
	int rig = 0;
	_q = 0;
	while(true){
		auto v = ask(j);
		_q ++;
		if(v[0] + v[1] == 0){
			return j;
		}
		if(n - v[0] - v[1] > n / 2){
			rig = v[1];
			break;
		}
		j ++;
	}
	while(j < n - 1){
		int l = j, r = n;
		while(r - l > 1){
			int m = (l + r) / 2;
			vector<int> v = ask(m);
			if(v[0] + v[1] == 0){
				return m;
			}
			if(v[1] == rig){
				l = m;
			}else r = m;
		}
		j = r + 1;
		rig --;
	}
	return n - 1;	
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 428 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 424 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 0 ms 428 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 428 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 424 KB Output is correct
7 Correct 0 ms 424 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 428 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 3 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 5 ms 344 KB Output is correct
16 Partially correct 32 ms 344 KB Partially correct - number of queries: 6551
17 Correct 0 ms 344 KB Output is correct
18 Partially correct 32 ms 344 KB Partially correct - number of queries: 7666
19 Correct 0 ms 424 KB Output is correct
20 Correct 8 ms 348 KB Output is correct
21 Correct 13 ms 424 KB Output is correct
22 Correct 3 ms 428 KB Output is correct
23 Correct 0 ms 428 KB Output is correct
24 Correct 0 ms 428 KB Output is correct
25 Correct 23 ms 348 KB Output is correct
26 Correct 19 ms 344 KB Output is correct
27 Correct 0 ms 432 KB Output is correct
28 Partially correct 27 ms 344 KB Partially correct - number of queries: 7311
29 Partially correct 28 ms 344 KB Partially correct - number of queries: 5553
30 Partially correct 32 ms 344 KB Partially correct - number of queries: 7616
31 Correct 0 ms 428 KB Output is correct
32 Correct 2 ms 344 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 12 ms 424 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 7 ms 352 KB Output is correct
37 Correct 1 ms 352 KB Output is correct
38 Correct 1 ms 352 KB Output is correct
39 Correct 22 ms 352 KB Output is correct
40 Partially correct 25 ms 348 KB Partially correct - number of queries: 6507
41 Correct 17 ms 344 KB Output is correct
42 Correct 26 ms 344 KB Output is correct
43 Correct 15 ms 344 KB Output is correct
44 Correct 7 ms 344 KB Output is correct
45 Correct 9 ms 344 KB Output is correct
46 Correct 1 ms 344 KB Output is correct
47 Correct 11 ms 344 KB Output is correct
48 Partially correct 32 ms 344 KB Partially correct - number of queries: 5693
49 Correct 4 ms 344 KB Output is correct
50 Partially correct 26 ms 344 KB Partially correct - number of queries: 7663
51 Correct 14 ms 344 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 1 ms 424 KB Output is correct
54 Correct 14 ms 344 KB Output is correct
55 Correct 0 ms 344 KB Output is correct
56 Partially correct 35 ms 344 KB Partially correct - number of queries: 7665
57 Partially correct 19 ms 344 KB Partially correct - number of queries: 5627
58 Partially correct 25 ms 344 KB Partially correct - number of queries: 5721
59 Correct 14 ms 344 KB Output is correct
60 Correct 18 ms 344 KB Output is correct
61 Correct 1 ms 344 KB Output is correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 1 ms 344 KB Output is correct
64 Correct 0 ms 344 KB Output is correct
65 Correct 0 ms 344 KB Output is correct
66 Correct 4 ms 344 KB Output is correct
67 Correct 0 ms 344 KB Output is correct
68 Correct 1 ms 424 KB Output is correct
69 Correct 4 ms 344 KB Output is correct
70 Correct 1 ms 344 KB Output is correct
71 Partially correct 36 ms 344 KB Partially correct - number of queries: 7790
72 Correct 3 ms 344 KB Output is correct
73 Partially correct 33 ms 344 KB Partially correct - number of queries: 7690
74 Partially correct 26 ms 344 KB Partially correct - number of queries: 7728
75 Correct 1 ms 344 KB Output is correct
76 Partially correct 20 ms 344 KB Partially correct - number of queries: 6660
77 Partially correct 29 ms 344 KB Partially correct - number of queries: 7678
78 Correct 1 ms 344 KB Output is correct
79 Correct 17 ms 344 KB Output is correct
80 Partially correct 35 ms 344 KB Partially correct - number of queries: 7683
81 Partially correct 29 ms 344 KB Partially correct - number of queries: 7660
82 Partially correct 29 ms 344 KB Partially correct - number of queries: 7600
83 Correct 1 ms 344 KB Output is correct
84 Partially correct 19 ms 344 KB Partially correct - number of queries: 6271
85 Partially correct 30 ms 344 KB Partially correct - number of queries: 7682
86 Correct 1 ms 344 KB Output is correct
87 Incorrect 1 ms 344 KB answer is not correct
88 Halted 0 ms 0 KB -