Submission #785866

#	Time	Username	Problem	Language	Result	Execution time	Memory
785866		aymanrs	The Big Prize (IOI17_prize)	C++14	97.66 / 100	52 ms	336 KiB

prize

#include<bits/stdc++.h>
using namespace std;
vector<int> ask(int i);/*{
	cout << i << '\n';
	vector<int> a(2);
	cin >> a[0] >> a[1];
	return a;
}*/
int clol, ans;
bool wegood = false;
void solve(int l, int r, int lpl, int lpr){
	int m = l+r>>1;
	auto a = ask(m);
	if(a[0]+a[1] == 0) {
		ans = m;
		wegood = true;
		return;
	}
	if(a[0]+a[1] == clol){
		if(a[0] > lpl && l < m) solve(l, m-1, lpl, a[1]);
		if(wegood) return;
		if(a[1] > lpr && r > m) solve(m+1, r, a[0], lpr);
		return;
	}
	int L = m-1, R = m+1;
	while(R < r){
		auto a = ask(R);
		if(a[0]+a[1]==0){
			ans = R;
			wegood = true;
			return;
		}
		if(a[0]+a[1]==clol){
			if(a[1] > lpr && R < r) solve(R+1, r, a[0], lpr);
			if(wegood) return;
			break;
		}
		R++;
	}
	while(L > l){
		auto a = ask(L);
		if(a[0]+a[1]==0){
			ans = L;
			wegood = true;
			return;
		}
		if(a[0]+a[1]==clol){
			if(a[0] > lpl && L > l) solve(l, L-1, lpl, a[1]);
			if(wegood) return;
			break;
		}
		L--;
	}
}
int find_best(int n){
	pair<int, pair<int, int>> lol = {0,{0, 0}};
	for(int i = 0;i < 475;i++){
		auto a = ask(i);
		if(a[0]+a[1] == 0) return i;
		lol = max(lol, make_pair(a[0]+a[1], make_pair(a[0], i)));
	}
	clol = lol.first;
	solve(lol.second.second+1, n-1, lol.second.first, 0);
	return ans;
}/*
int main(){
	int n;
	cin >> n;
	cout << find_best(n) << '\n';
}*/

Compilation message (stderr)

prize.cpp: In function 'void solve(int, int, int, int)':
prize.cpp:12:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  int m = l+r>>1;
      |          ~^~

• Subtask 1: 20 / 20
• Subtask 2: 77.66 / 80