oj.uz

Submission #975153

# Submission time Handle Problem Language Result Execution time Memory
975153 2024-05-04T13:51:43 Z StefanSebez The Big Prize (IOI17_prize) C++14
20 / 100
 54 ms 1632 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(0));
int find_best(int n){
	int ct=300,V=n;
	while(ct--){
		int x=rng()%n;
		vector<int>tmp=ask(x);
		if(n-(tmp[0]+tmp[1])<V) V=n-(tmp[0]+tmp[1]);
	}
	int res=-1;
	set<int>st;
	st.insert(-1),st.insert(n);
	auto it=st.begin();
	int sajz=0;
	while(it!=st.end()){
		auto it2=it;
		int i=*it;
		//if(res!=-1 && res==i) break;
		it++;
		if(it==st.end()) break;
		int j=*it;
		int l=i+1,r=j-1;
		//printf("%i %i %i\n",i,j,sajz);
		while(l<=r){
			int mid=(l+r)/2;
			vector<int>tmp=ask(mid);
			if(n-tmp[0]-tmp[1]!=V){
				if(tmp[0]==0 && tmp[1]==0) res=mid;
				st.insert(mid);
				r=mid-1;
				continue;
			}
			if(tmp[0]>=1+sajz) r=mid-1;
			else l=mid+1;
		}
		it=it2;
		it++;
		sajz++;
	}
	//for(auto i=st.begin();i!=st.end();i++) printf("%i ",*i);
	//printf("\n");
	/*for(int i = 0; i < n; i++) {
		std::vector<int> res = ask(i);
		if(res[0] + res[1] == 0)
			return i;
	}*/
	return res;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 11 ms 696 KB Output is correct
15 Partially correct 47 ms 680 KB Partially correct - number of queries: 7567
16 Partially correct 34 ms 444 KB Partially correct - number of queries: 7965
17 Partially correct 37 ms 436 KB Partially correct - number of queries: 7978
18 Partially correct 46 ms 688 KB Partially correct - number of queries: 7978
19 Partially correct 39 ms 688 KB Partially correct - number of queries: 7484
20 Partially correct 36 ms 436 KB Partially correct - number of queries: 5244
21 Partially correct 41 ms 700 KB Partially correct - number of queries: 6787
22 Partially correct 30 ms 680 KB Partially correct - number of queries: 5701
23 Correct 2 ms 344 KB Output is correct
24 Correct 4 ms 344 KB Output is correct
25 Partially correct 38 ms 684 KB Partially correct - number of queries: 7356
26 Partially correct 28 ms 440 KB Partially correct - number of queries: 7667
27 Correct 2 ms 344 KB Output is correct
28 Partially correct 31 ms 692 KB Partially correct - number of queries: 6992
29 Partially correct 28 ms 436 KB Partially correct - number of queries: 5773
30 Partially correct 36 ms 700 KB Partially correct - number of queries: 7903
31 Partially correct 32 ms 680 KB Partially correct - number of queries: 7894
32 Correct 3 ms 344 KB Output is correct
33 Correct 2 ms 344 KB Output is correct
34 Partially correct 34 ms 704 KB Partially correct - number of queries: 7411
35 Correct 3 ms 344 KB Output is correct
36 Partially correct 34 ms 940 KB Partially correct - number of queries: 7293
37 Correct 4 ms 344 KB Output is correct
38 Correct 2 ms 344 KB Output is correct
39 Partially correct 37 ms 948 KB Partially correct - number of queries: 7898
40 Partially correct 30 ms 444 KB Partially correct - number of queries: 6800
41 Partially correct 38 ms 684 KB Partially correct - number of queries: 7718
42 Partially correct 47 ms 696 KB Partially correct - number of queries: 7718
43 Partially correct 38 ms 444 KB Partially correct - number of queries: 7107
44 Partially correct 33 ms 684 KB Partially correct - number of queries: 7353
45 Partially correct 38 ms 684 KB Partially correct - number of queries: 7606
46 Partially correct 36 ms 700 KB Partially correct - number of queries: 7991
47 Partially correct 29 ms 452 KB Partially correct - number of queries: 7448
48 Partially correct 41 ms 456 KB Partially correct - number of queries: 7972
49 Partially correct 41 ms 444 KB Partially correct - number of queries: 7598
50 Partially correct 32 ms 444 KB Partially correct - number of queries: 7972
51 Partially correct 31 ms 436 KB Partially correct - number of queries: 7287
52 Partially correct 44 ms 680 KB Partially correct - number of queries: 7972
53 Correct 2 ms 344 KB Output is correct
54 Partially correct 37 ms 952 KB Partially correct - number of queries: 7827
55 Partially correct 37 ms 440 KB Partially correct - number of queries: 7970
56 Partially correct 30 ms 440 KB Partially correct - number of queries: 7971
57 Partially correct 27 ms 448 KB Partially correct - number of queries: 7715
58 Partially correct 37 ms 440 KB Partially correct - number of queries: 6881
59 Partially correct 33 ms 444 KB Partially correct - number of queries: 7719
60 Partially correct 28 ms 684 KB Partially correct - number of queries: 6520
61 Correct 2 ms 344 KB Output is correct
62 Correct 2 ms 596 KB Output is correct
63 Correct 2 ms 344 KB Output is correct
64 Correct 3 ms 344 KB Output is correct
65 Correct 2 ms 344 KB Output is correct
66 Correct 4 ms 716 KB Output is correct
67 Correct 3 ms 704 KB Output is correct
68 Correct 5 ms 696 KB Output is correct
69 Correct 3 ms 704 KB Output is correct
70 Correct 3 ms 444 KB Output is correct
71 Partially correct 36 ms 1188 KB Partially correct - number of queries: 8178
72 Correct 3 ms 344 KB Output is correct
73 Partially correct 39 ms 944 KB Partially correct - number of queries: 8065
74 Partially correct 40 ms 436 KB Partially correct - number of queries: 8114
75 Correct 2 ms 344 KB Output is correct
76 Partially correct 32 ms 444 KB Partially correct - number of queries: 6980
77 Partially correct 33 ms 700 KB Partially correct - number of queries: 7406
78 Correct 3 ms 344 KB Output is correct
79 Correct 25 ms 688 KB Output is correct
80 Partially correct 30 ms 952 KB Partially correct - number of queries: 7068
81 Partially correct 40 ms 1180 KB Partially correct - number of queries: 7722
82 Partially correct 33 ms 692 KB Partially correct - number of queries: 7639
83 Correct 2 ms 344 KB Output is correct
84 Partially correct 30 ms 940 KB Partially correct - number of queries: 6258
85 Partially correct 37 ms 692 KB Partially correct - number of queries: 7372
86 Partially correct 26 ms 684 KB Partially correct - number of queries: 5092
87 Correct 3 ms 344 KB Output is correct
88 Correct 22 ms 440 KB Output is correct
89 Partially correct 24 ms 944 KB Partially correct - number of queries: 5055
90 Correct 2 ms 344 KB Output is correct
91 Correct 18 ms 696 KB Output is correct
92 Correct 23 ms 696 KB Output is correct
93 Incorrect 54 ms 1632 KB Incorrect
94 Halted 0 ms 0 KB -