Submission #70136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
70136	2018-08-22T11:44:24 Z	E869120	The Big Prize (IOI17_prize)	C++14	20 / 100	83 ms	588 KB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int Rand(){
	int G=0;
	for(int i=0;i<30;i++){G+=(1<<i)*(rand()%2);}
	return G;
}

int find_best(int n) {
	int maxn=0;
	for(int i=0;i<100;i++){
		vector<int>p=ask(rand()%n);
		maxn=max(maxn,p[0]+p[1]);
	}
	int cx=0;
	for(int i=0;i<maxn;i++){
		int L=cx,R=n+1,M,res=cx-1;
		for(int j=0;j<21;j++){
			M=(L+R)/2;int MM=min(M,n-1);
			vector<int>p=ask(MM);
			if(p[0]+p[1]==maxn && p[0]==i){res=max(res,MM);L=MM;}
			else{R=MM;}
		}
		vector<int>p=ask(res+1);
		if(p[0]==0 && p[1]==0) return res+1;
		cx=res+2;
	}
	return -1;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	288 KB	Output is correct
2	Correct	5 ms	308 KB	Output is correct
3	Correct	5 ms	344 KB	Output is correct
4	Correct	4 ms	344 KB	Output is correct
5	Correct	4 ms	428 KB	Output is correct
6	Correct	3 ms	444 KB	Output is correct
7	Correct	5 ms	468 KB	Output is correct
8	Correct	4 ms	520 KB	Output is correct
9	Correct	2 ms	544 KB	Output is correct
10	Correct	4 ms	544 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	564 KB	Output is correct
2	Correct	3 ms	568 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct
4	Correct	6 ms	568 KB	Output is correct
5	Correct	5 ms	568 KB	Output is correct
6	Correct	3 ms	576 KB	Output is correct
7	Correct	4 ms	580 KB	Output is correct
8	Correct	4 ms	580 KB	Output is correct
9	Correct	2 ms	580 KB	Output is correct
10	Correct	3 ms	588 KB	Output is correct
11	Correct	4 ms	588 KB	Output is correct
12	Correct	4 ms	588 KB	Output is correct
13	Correct	10 ms	588 KB	Output is correct
14	Correct	9 ms	588 KB	Output is correct
15	Correct	14 ms	588 KB	Output is correct
16	Partially correct	83 ms	588 KB	Partially correct - number of queries: 8702
17	Correct	3 ms	588 KB	Output is correct
18	Incorrect	82 ms	588 KB	Incorrect
19	Halted	0 ms	0 KB	-