oj.uz

Submission #797421

# Submission time Handle Problem Language Result Execution time Memory
797421 2023-07-29T10:56:47 Z WongChun1234 The Big Prize (IOI17_prize) C++14
90 / 100
 77 ms 2816 KB 
#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int N=200050;
const bool DEBUG=0;
int n,l,r,lbound,rbound,mid,done[N],mx;
pair<int,int> res[N];
vector<int> pos,apos;

pair<int,int> qry(int id){
	if (id>=n||id<0) return {-1,-1};
	if (done[id]) return res[id];
	vector<int> resp=ask(id);
	done[id]=1;
	res[id]={resp[0],resp[1]};
	return res[id];
}

int sum(int id){
	return qry(id).first+qry(id).second;
}

int find_best(int N) {
	n=N;
	if (n<=5000&&(!DEBUG)){
		for (int i=0;i<n;i++){
			if (sum(i)==0) return i;
		}
	}
	for (int i=0;i<min(712,n);i++){
		mx=max(mx,sum(i));
	}
	pos.push_back(-1);
	for (int i=0;i<min(712,n);i++){
		if (sum(i)<mx) pos.push_back(i),apos.push_back(i);
	}
	pos.push_back(n);
	if (DEBUG) mx=3;
	if (DEBUG) pos={-1,6};
	if (DEBUG) for (int i:pos) cout<<i<<"!\n";
	for (int i=1;i<pos.size();i++){
		l=pos[i-1]+1,r=pos[i]-1;
		while (l<=r&&sum(l)<mx) l++;
		while (l<=r&&sum(r)<mx) r--;
		if (DEBUG) cout<<"start "<<l<<" "<<r<<"\n";
		while (qry(l).first!=qry(r).first){
			if (DEBUG) cout<<l<<"-"<<r<<"\n";
			if (r-l+1<=3){
				for (int j=l;j<=r;j++) res[j]=qry(j);
				break;
			}
			lbound=l,rbound=r-1;
			//goal: find last ==l.first
			while (lbound<rbound){
				mid=(lbound+rbound)/2;
				while (sum(mid)<mx) mid--;
				if (mid==lbound) break;
				if (qry(mid).first==qry(l).first) lbound=mid;
				else rbound=mid-1;
			}
			if (DEBUG) cout<<"found "<<lbound+1<<"\n";
			assert(sum(lbound+1)<mx);
			l=lbound+2;
			while (l<=r&&sum(l)<mx) l++;
			while (l<=r&&sum(r)<mx) r--;
		}
	}
	for (int i=0;i<n;i++){
		if (done[i]&&sum(i)==0) return i;
	}
	return -1;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for (int i=1;i<pos.size();i++){
      |               ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Output is correct
2 Correct 4 ms 320 KB Output is correct
3 Correct 3 ms 316 KB Output is correct
4 Correct 3 ms 320 KB Output is correct
5 Correct 4 ms 336 KB Output is correct
6 Correct 6 ms 300 KB Output is correct
7 Correct 3 ms 320 KB Output is correct
8 Correct 3 ms 320 KB Output is correct
9 Correct 4 ms 324 KB Output is correct
10 Correct 5 ms 336 KB Output is correct

Subtask #2
70.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 312 KB Output is correct
2 Correct 7 ms 328 KB Output is correct
3 Correct 7 ms 304 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 3 ms 320 KB Output is correct
6 Correct 6 ms 320 KB Output is correct
7 Correct 3 ms 352 KB Output is correct
8 Correct 7 ms 336 KB Output is correct
9 Correct 5 ms 328 KB Output is correct
10 Correct 5 ms 320 KB Output is correct
11 Correct 10 ms 1556 KB Output is correct
12 Correct 12 ms 1616 KB Output is correct
13 Correct 5 ms 1568 KB Output is correct
14 Correct 22 ms 472 KB Output is correct
15 Partially correct 69 ms 2572 KB Partially correct - number of queries: 8067
16 Partially correct 30 ms 2596 KB Partially correct - number of queries: 8490
17 Partially correct 53 ms 2604 KB Partially correct - number of queries: 8491
18 Partially correct 30 ms 2596 KB Partially correct - number of queries: 8476
19 Partially correct 46 ms 2780 KB Partially correct - number of queries: 8016
20 Partially correct 33 ms 1404 KB Partially correct - number of queries: 5718
21 Partially correct 29 ms 2616 KB Partially correct - number of queries: 8389
22 Partially correct 57 ms 2504 KB Partially correct - number of queries: 6419
23 Correct 3 ms 704 KB Output is correct
24 Correct 13 ms 1572 KB Output is correct
25 Partially correct 30 ms 2604 KB Partially correct - number of queries: 8399
26 Partially correct 72 ms 2524 KB Partially correct - number of queries: 8326
27 Correct 4 ms 704 KB Output is correct
28 Partially correct 59 ms 2612 KB Partially correct - number of queries: 8261
29 Partially correct 66 ms 2632 KB Partially correct - number of queries: 6901
30 Partially correct 60 ms 2624 KB Partially correct - number of queries: 8437
31 Partially correct 72 ms 2668 KB Partially correct - number of queries: 8438
32 Correct 5 ms 1588 KB Output is correct
33 Correct 0 ms 312 KB Output is correct
34 Partially correct 30 ms 2592 KB Partially correct - number of queries: 8488
35 Correct 4 ms 1068 KB Output is correct
36 Partially correct 54 ms 2560 KB Partially correct - number of queries: 8404
37 Correct 5 ms 1576 KB Output is correct
38 Correct 3 ms 740 KB Output is correct
39 Partially correct 69 ms 2588 KB Partially correct - number of queries: 8435
40 Partially correct 64 ms 2596 KB Partially correct - number of queries: 7310
41 Partially correct 32 ms 2608 KB Partially correct - number of queries: 8372
42 Partially correct 43 ms 2596 KB Partially correct - number of queries: 8372
43 Partially correct 62 ms 2604 KB Partially correct - number of queries: 7972
44 Partially correct 30 ms 2716 KB Partially correct - number of queries: 8480
45 Partially correct 42 ms 2572 KB Partially correct - number of queries: 8450
46 Partially correct 66 ms 2628 KB Partially correct - number of queries: 8492
47 Partially correct 41 ms 2600 KB Partially correct - number of queries: 8465
48 Partially correct 68 ms 2580 KB Partially correct - number of queries: 8490
49 Partially correct 76 ms 2596 KB Partially correct - number of queries: 8464
50 Partially correct 31 ms 2592 KB Partially correct - number of queries: 8494
51 Partially correct 31 ms 2592 KB Partially correct - number of queries: 8443
52 Partially correct 61 ms 2816 KB Partially correct - number of queries: 8506
53 Correct 6 ms 696 KB Output is correct
54 Partially correct 33 ms 2616 KB Partially correct - number of queries: 8412
55 Partially correct 30 ms 2600 KB Partially correct - number of queries: 8490
56 Partially correct 53 ms 2636 KB Partially correct - number of queries: 8495
57 Partially correct 52 ms 2592 KB Partially correct - number of queries: 8438
58 Partially correct 76 ms 2632 KB Partially correct - number of queries: 8440
59 Partially correct 70 ms 2612 KB Partially correct - number of queries: 8367
60 Partially correct 48 ms 2592 KB Partially correct - number of queries: 8006
61 Correct 6 ms 676 KB Output is correct
62 Correct 7 ms 592 KB Output is correct
63 Correct 5 ms 672 KB Output is correct
64 Correct 8 ms 672 KB Output is correct
65 Correct 7 ms 276 KB Output is correct
66 Correct 5 ms 312 KB Output is correct
67 Correct 10 ms 296 KB Output is correct
68 Correct 5 ms 296 KB Output is correct
69 Correct 4 ms 352 KB Output is correct
70 Correct 9 ms 296 KB Output is correct
71 Partially correct 73 ms 2612 KB Partially correct - number of queries: 8950
72 Correct 10 ms 1744 KB Output is correct
73 Partially correct 38 ms 2608 KB Partially correct - number of queries: 8833
74 Partially correct 53 ms 2584 KB Partially correct - number of queries: 8872
75 Correct 7 ms 708 KB Output is correct
76 Partially correct 67 ms 2504 KB Partially correct - number of queries: 7706
77 Partially correct 57 ms 2524 KB Partially correct - number of queries: 8667
78 Correct 7 ms 1744 KB Output is correct
79 Correct 32 ms 2624 KB Output is correct
80 Partially correct 77 ms 2560 KB Partially correct - number of queries: 8692
81 Partially correct 56 ms 2624 KB Partially correct - number of queries: 8681
82 Partially correct 50 ms 2564 KB Partially correct - number of queries: 8582
83 Correct 8 ms 696 KB Output is correct
84 Partially correct 59 ms 2504 KB Partially correct - number of queries: 7188
85 Partially correct 57 ms 2524 KB Partially correct - number of queries: 8628
86 Correct 4 ms 336 KB Output is correct
87 Correct 6 ms 304 KB Output is correct
88 Correct 7 ms 320 KB Output is correct
89 Correct 7 ms 336 KB Output is correct
90 Correct 7 ms 336 KB Output is correct
91 Correct 7 ms 320 KB Output is correct
92 Correct 7 ms 336 KB Output is correct
93 Correct 10 ms 1344 KB Output is correct
94 Correct 11 ms 1332 KB Output is correct
95 Correct 9 ms 1336 KB Output is correct
96 Correct 9 ms 1232 KB Output is correct
97 Correct 4 ms 320 KB Output is correct