Submission #103119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103119	2019-03-29T05:57:37 Z	minson123	The Big Prize (IOI17_prize)	C++11	20 / 100	80 ms	872 KB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int pos,minr,limt;
map<int,pii> dic;
pii query(int p){
	if(dic.find(p)!=dic.end()) return dic[p];
	vector<int> q=ask(p);
	return dic[p]=pii(q[0],q[1]);
}
void solve(int l,int r){
	/*pii q=query(l);
	if(q.first+q.second==limt && q.second==minr) return;*/
	if(pos!=-1) return;
	if(l==r){
		pii q=query(l);
		if(q.first==0 && q.second==0) pos=l;
		else if(q.first+q.second==limt) minr=q.second;
	}else{
		int mid=(l+r)>>1;
		pii q=query(mid+1);
		if(q.first+q.second<limt || q.second>minr) solve(mid+1,r);
		solve(l,mid);
	}
}
int find_best(int n){
	srand(time(nullptr));
	for(int i=0;i<10;i++){
		int p=rand()%n;
		pii q=query(p);
		limt=max(limt,q.first+q.second);
	}
	minr=pos=-1;
	solve(0,n-1);
	return pos;
}

Subtask #1

20.0 / 20.0

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

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	3 ms	392 KB	Output is correct
3	Correct	3 ms	392 KB	Output is correct
4	Correct	3 ms	256 KB	Output is correct
5	Correct	3 ms	392 KB	Output is correct
6	Correct	3 ms	528 KB	Output is correct
7	Correct	3 ms	256 KB	Output is correct
8	Correct	2 ms	400 KB	Output is correct
9	Correct	3 ms	256 KB	Output is correct
10	Correct	4 ms	256 KB	Output is correct
11	Correct	12 ms	384 KB	Output is correct
12	Correct	16 ms	512 KB	Output is correct
13	Correct	3 ms	256 KB	Output is correct
14	Correct	23 ms	504 KB	Output is correct
15	Incorrect	80 ms	872 KB	Incorrect
16	Halted	0 ms	0 KB	-