oj.uz

Submission #478694

# Submission time Handle Problem Language Result Execution time Memory
478694 2021-10-08T07:23:21 Z mosiashvililuka The Big Prize (IOI17_prize) C++14
90 / 100
 128 ms 2780 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,lef,rig,mid,T=550,BO[200009],mx,E;
pair <int, int> P[200009];vector <int> vv;
void ASK(int q){
	if(q==0) return;
	if(BO[q]==0){
		BO[q]=1;vv=ask(q-1);
		P[q]=make_pair(vv[0],vv[1]);
	}
}
int find_best(int Nn) {
	a=Nn;
	for(i=1; i<=min(T,a); i++){
		ASK(i);
		mx=max(mx,P[i].first+P[i].second);
	}
	ASK(a);i=0;
	j=a;
	while(P[j].first+P[j].second!=mx){
		j--;ASK(j);
	}
	E=P[j].first;jj=j;
	while(1){
		if(i>=jj||P[i].first==E) break;
		lef=i;rig=jj+1;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			ASK(mid);j=mid;
			while(P[j].first+P[j].second!=mx&&j!=0){
				j--;ASK(j);
			}
			if(P[j].first==P[i].first){
				lef=mid;
			}else{
				rig=mid;
			}
		}
		//rig-1 > lollipop
		ASK(rig-1);
		i=rig;ASK(i);
		while(i<jj&&P[i].first+P[i].second!=mx){
			i++;ASK(i);
		}
	}
	for(i=1; i<=a; i++){
		if(BO[i]!=0&&P[i].first==0&&P[i].second==0){
			return i-1;
		}
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 320 KB Output is correct
2 Correct 7 ms 288 KB Output is correct
3 Correct 6 ms 328 KB Output is correct
4 Correct 10 ms 292 KB Output is correct
5 Correct 5 ms 328 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 7 ms 288 KB Output is correct
8 Correct 7 ms 292 KB Output is correct
9 Correct 6 ms 320 KB Output is correct
10 Correct 6 ms 328 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 328 KB Output is correct
2 Correct 7 ms 272 KB Output is correct
3 Correct 5 ms 304 KB Output is correct
4 Correct 3 ms 300 KB Output is correct
5 Correct 7 ms 292 KB Output is correct
6 Correct 6 ms 328 KB Output is correct
7 Correct 5 ms 292 KB Output is correct
8 Correct 7 ms 320 KB Output is correct
9 Correct 3 ms 300 KB Output is correct
10 Correct 7 ms 328 KB Output is correct
11 Correct 13 ms 1600 KB Output is correct
12 Correct 7 ms 1652 KB Output is correct
13 Correct 7 ms 1692 KB Output is correct
14 Correct 17 ms 596 KB Output is correct
15 Partially correct 75 ms 2600 KB Partially correct - number of queries: 7940
16 Partially correct 104 ms 2592 KB Partially correct - number of queries: 8368
17 Partially correct 73 ms 2588 KB Partially correct - number of queries: 8356
18 Partially correct 81 ms 2572 KB Partially correct - number of queries: 8349
19 Partially correct 81 ms 2544 KB Partially correct - number of queries: 7862
20 Partially correct 51 ms 1456 KB Partially correct - number of queries: 5587
21 Partially correct 78 ms 2576 KB Partially correct - number of queries: 8247
22 Partially correct 93 ms 2616 KB Partially correct - number of queries: 6288
23 Correct 7 ms 584 KB Output is correct
24 Correct 9 ms 1568 KB Output is correct
25 Partially correct 128 ms 2596 KB Partially correct - number of queries: 8262
26 Partially correct 88 ms 2524 KB Partially correct - number of queries: 8196
27 Correct 9 ms 664 KB Output is correct
28 Partially correct 65 ms 2504 KB Partially correct - number of queries: 8144
29 Partially correct 65 ms 2508 KB Partially correct - number of queries: 6750
30 Partially correct 101 ms 2496 KB Partially correct - number of queries: 8297
31 Partially correct 58 ms 2616 KB Partially correct - number of queries: 8296
32 Correct 15 ms 1648 KB Output is correct
33 Correct 2 ms 200 KB Output is correct
34 Partially correct 84 ms 2576 KB Partially correct - number of queries: 8338
35 Correct 5 ms 1056 KB Output is correct
36 Partially correct 93 ms 2616 KB Partially correct - number of queries: 8249
37 Correct 10 ms 1448 KB Output is correct
38 Correct 7 ms 664 KB Output is correct
39 Partially correct 65 ms 2608 KB Partially correct - number of queries: 8279
40 Partially correct 75 ms 2780 KB Partially correct - number of queries: 7186
41 Partially correct 63 ms 2600 KB Partially correct - number of queries: 8216
42 Partially correct 41 ms 2632 KB Partially correct - number of queries: 8216
43 Partially correct 70 ms 2644 KB Partially correct - number of queries: 7815
44 Partially correct 65 ms 2604 KB Partially correct - number of queries: 8333
45 Partially correct 100 ms 2588 KB Partially correct - number of queries: 8285
46 Partially correct 81 ms 2640 KB Partially correct - number of queries: 8349
47 Partially correct 39 ms 2620 KB Partially correct - number of queries: 8335
48 Partially correct 102 ms 2544 KB Partially correct - number of queries: 8344
49 Partially correct 97 ms 2544 KB Partially correct - number of queries: 8309
50 Partially correct 64 ms 2604 KB Partially correct - number of queries: 8347
51 Partially correct 96 ms 2680 KB Partially correct - number of queries: 8311
52 Partially correct 83 ms 2664 KB Partially correct - number of queries: 8374
53 Correct 4 ms 684 KB Output is correct
54 Partially correct 52 ms 2612 KB Partially correct - number of queries: 8282
55 Partially correct 81 ms 2620 KB Partially correct - number of queries: 8354
56 Partially correct 63 ms 2496 KB Partially correct - number of queries: 8343
57 Partially correct 61 ms 2568 KB Partially correct - number of queries: 8276
58 Partially correct 92 ms 2644 KB Partially correct - number of queries: 8307
59 Partially correct 58 ms 2564 KB Partially correct - number of queries: 8206
60 Partially correct 36 ms 2612 KB Partially correct - number of queries: 7841
61 Correct 9 ms 672 KB Output is correct
62 Correct 7 ms 656 KB Output is correct
63 Correct 7 ms 576 KB Output is correct
64 Correct 7 ms 668 KB Output is correct
65 Correct 9 ms 284 KB Output is correct
66 Correct 13 ms 320 KB Output is correct
67 Correct 5 ms 304 KB Output is correct
68 Correct 6 ms 296 KB Output is correct
69 Correct 12 ms 200 KB Output is correct
70 Correct 9 ms 200 KB Output is correct
71 Partially correct 95 ms 2620 KB Partially correct - number of queries: 8298
72 Correct 15 ms 1712 KB Output is correct
73 Partially correct 74 ms 2620 KB Partially correct - number of queries: 8188
74 Partially correct 76 ms 2560 KB Partially correct - number of queries: 8233
75 Correct 8 ms 680 KB Output is correct
76 Partially correct 74 ms 2588 KB Partially correct - number of queries: 7168
77 Partially correct 89 ms 2576 KB Partially correct - number of queries: 8393
78 Correct 11 ms 1632 KB Output is correct
79 Correct 41 ms 2512 KB Output is correct
80 Partially correct 71 ms 2548 KB Partially correct - number of queries: 8388
81 Partially correct 102 ms 2548 KB Partially correct - number of queries: 8404
82 Partially correct 70 ms 2580 KB Partially correct - number of queries: 8331
83 Correct 5 ms 696 KB Output is correct
84 Partially correct 58 ms 2632 KB Partially correct - number of queries: 6946
85 Partially correct 98 ms 2500 KB Partially correct - number of queries: 8367
86 Correct 8 ms 300 KB Output is correct
87 Correct 6 ms 308 KB Output is correct
88 Correct 10 ms 308 KB Output is correct
89 Correct 6 ms 308 KB Output is correct
90 Correct 3 ms 312 KB Output is correct
91 Correct 6 ms 308 KB Output is correct
92 Correct 4 ms 308 KB Output is correct
93 Correct 12 ms 1320 KB Output is correct
94 Correct 10 ms 1392 KB Output is correct
95 Correct 8 ms 1332 KB Output is correct
96 Correct 5 ms 1332 KB Output is correct
97 Correct 8 ms 308 KB Output is correct