oj.uz

Submission #975161

# Submission time Handle Problem Language Result Execution time Memory
975161 2024-05-04T14:02:40 Z StefanSebez The Big Prize (IOI17_prize) C++14
20 / 100
 58 ms 3280 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
mt19937 rng(time(0));
int find_best(int n){
	pair<int,int> temp[n+10];
	for(int i=0;i<n;i++) temp[i].fi=temp[i].se=-1;
	int ct=300,V=n;
	while(ct--){
		int x=rng()%n;
		vector<int>tmp;
		if(temp[x].fi==-1) tmp=ask(x);
		else tmp.pb(temp[x].fi),tmp.pb(temp[x].se);
		temp[x]={tmp[0],tmp[1]};
		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;
			if(temp[mid].fi==-1) tmp=ask(mid);
			else tmp.pb(temp[mid].fi),tmp.pb(temp[mid].se);
			temp[mid]={tmp[0],tmp[1]};
			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++){
		int x=*i;
		if(x==-1 || x==n) continue;
		if(temp[x].fi==0 && temp[x].se==0) res=x;
	}
	//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 3 ms 1880 KB Output is correct
2 Correct 2 ms 1880 KB Output is correct
3 Correct 3 ms 1880 KB Output is correct
4 Correct 3 ms 1880 KB Output is correct
5 Correct 4 ms 1880 KB Output is correct
6 Correct 3 ms 1880 KB Output is correct
7 Correct 4 ms 1880 KB Output is correct
8 Correct 3 ms 1880 KB Output is correct
9 Correct 3 ms 1880 KB Output is correct
10 Correct 3 ms 1880 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1880 KB Output is correct
2 Correct 3 ms 1880 KB Output is correct
3 Correct 3 ms 1880 KB Output is correct
4 Correct 3 ms 2132 KB Output is correct
5 Correct 3 ms 1880 KB Output is correct
6 Correct 3 ms 1880 KB Output is correct
7 Correct 3 ms 1880 KB Output is correct
8 Correct 3 ms 1880 KB Output is correct
9 Correct 3 ms 1960 KB Output is correct
10 Correct 2 ms 1880 KB Output is correct
11 Correct 4 ms 2132 KB Output is correct
12 Correct 5 ms 1880 KB Output is correct
13 Correct 7 ms 1880 KB Output is correct
14 Correct 10 ms 600 KB Output is correct
15 Partially correct 37 ms 2260 KB Partially correct - number of queries: 7493
16 Partially correct 46 ms 2248 KB Partially correct - number of queries: 7904
17 Partially correct 37 ms 2008 KB Partially correct - number of queries: 7916
18 Partially correct 49 ms 2504 KB Partially correct - number of queries: 7903
19 Partially correct 44 ms 2256 KB Partially correct - number of queries: 7438
20 Partially correct 25 ms 1220 KB Partially correct - number of queries: 5186
21 Partially correct 31 ms 2252 KB Partially correct - number of queries: 6658
22 Partially correct 29 ms 2260 KB Partially correct - number of queries: 5657
23 Correct 3 ms 1880 KB Output is correct
24 Correct 4 ms 1880 KB Output is correct
25 Partially correct 32 ms 2012 KB Partially correct - number of queries: 7270
26 Partially correct 35 ms 2256 KB Partially correct - number of queries: 7568
27 Correct 3 ms 1880 KB Output is correct
28 Partially correct 39 ms 2008 KB Partially correct - number of queries: 6907
29 Partially correct 24 ms 2008 KB Partially correct - number of queries: 5712
30 Partially correct 46 ms 2008 KB Partially correct - number of queries: 7841
31 Partially correct 58 ms 2004 KB Partially correct - number of queries: 7842
32 Correct 6 ms 1880 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Partially correct 36 ms 2248 KB Partially correct - number of queries: 7329
35 Correct 4 ms 1880 KB Output is correct
36 Partially correct 44 ms 2248 KB Partially correct - number of queries: 7193
37 Correct 5 ms 1888 KB Output is correct
38 Correct 3 ms 1880 KB Output is correct
39 Partially correct 37 ms 2248 KB Partially correct - number of queries: 7840
40 Partially correct 36 ms 2008 KB Partially correct - number of queries: 6755
41 Partially correct 43 ms 2248 KB Partially correct - number of queries: 7639
42 Partially correct 35 ms 2256 KB Partially correct - number of queries: 7639
43 Partially correct 36 ms 2252 KB Partially correct - number of queries: 7001
44 Partially correct 33 ms 2008 KB Partially correct - number of queries: 7253
45 Partially correct 34 ms 2260 KB Partially correct - number of queries: 7493
46 Partially correct 39 ms 2248 KB Partially correct - number of queries: 7907
47 Partially correct 40 ms 2012 KB Partially correct - number of queries: 7352
48 Partially correct 29 ms 2240 KB Partially correct - number of queries: 7903
49 Partially correct 38 ms 2256 KB Partially correct - number of queries: 7507
50 Partially correct 29 ms 2264 KB Partially correct - number of queries: 7911
51 Partially correct 32 ms 2248 KB Partially correct - number of queries: 7181
52 Partially correct 43 ms 2136 KB Partially correct - number of queries: 7909
53 Correct 3 ms 1876 KB Output is correct
54 Partially correct 36 ms 2004 KB Partially correct - number of queries: 7759
55 Partially correct 35 ms 2516 KB Partially correct - number of queries: 7910
56 Partially correct 41 ms 2248 KB Partially correct - number of queries: 7908
57 Partially correct 40 ms 2268 KB Partially correct - number of queries: 7635
58 Partially correct 26 ms 2136 KB Partially correct - number of queries: 6738
59 Partially correct 35 ms 2016 KB Partially correct - number of queries: 7628
60 Partially correct 52 ms 2008 KB Partially correct - number of queries: 6469
61 Correct 3 ms 1880 KB Output is correct
62 Correct 4 ms 1888 KB Output is correct
63 Correct 4 ms 1880 KB Output is correct
64 Correct 3 ms 1876 KB Output is correct
65 Correct 3 ms 1880 KB Output is correct
66 Correct 5 ms 2264 KB Output is correct
67 Correct 5 ms 2264 KB Output is correct
68 Correct 4 ms 2004 KB Output is correct
69 Correct 4 ms 2260 KB Output is correct
70 Correct 4 ms 2012 KB Output is correct
71 Partially correct 42 ms 2248 KB Partially correct - number of queries: 8142
72 Correct 6 ms 1880 KB Output is correct
73 Partially correct 36 ms 2260 KB Partially correct - number of queries: 8011
74 Partially correct 37 ms 2248 KB Partially correct - number of queries: 8062
75 Correct 3 ms 1880 KB Output is correct
76 Partially correct 32 ms 2252 KB Partially correct - number of queries: 6934
77 Partially correct 33 ms 2264 KB Partially correct - number of queries: 7777
78 Correct 5 ms 1880 KB Output is correct
79 Correct 17 ms 2248 KB Output is correct
80 Partially correct 40 ms 2004 KB Partially correct - number of queries: 7278
81 Partially correct 39 ms 2244 KB Partially correct - number of queries: 7261
82 Partially correct 46 ms 2016 KB Partially correct - number of queries: 7381
83 Correct 3 ms 1880 KB Output is correct
84 Partially correct 37 ms 2248 KB Partially correct - number of queries: 6357
85 Partially correct 38 ms 2256 KB Partially correct - number of queries: 7401
86 Correct 24 ms 2260 KB Output is correct
87 Correct 6 ms 1880 KB Output is correct
88 Correct 22 ms 2520 KB Output is correct
89 Correct 22 ms 2260 KB Output is correct
90 Correct 3 ms 1880 KB Output is correct
91 Correct 18 ms 2260 KB Output is correct
92 Correct 22 ms 2236 KB Output is correct
93 Incorrect 50 ms 3280 KB Incorrect
94 Halted 0 ms 0 KB -