oj.uz

Submission #103114

# Submission time Handle Problem Language Result Execution time Memory
103114 2019-03-29T05:12:26 Z minson123 The Big Prize (IOI17_prize) C++11
0 / 100
 98 ms 936 KB 
#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){
	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=min(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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 936 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 888 KB Incorrect
2 Halted 0 ms 0 KB -