Submission #314508

#	Time	Username	Problem	Language	Result	Execution time	Memory
314508		anakib1	The Big Prize (IOI17_prize)	C++17	90 / 100	114 ms	416 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
int find_best(int n){
	int mx = 0;
	for(int i = 0 ; i < 500 ; ++i){
		vector < int > res = ask(i);
		if(res[0] + res[1] == 0){
			return i;
		}
		mx = max(mx , res[0] + res[1]);
	}
	int i = 500;
	while(i < n){
		vector < int > res = ask(i);
		if(res[0] + res[1] == 0){
			return i;
		}
		if(res[0] + res[1] == mx){
			int l = i + 1;
			int r = n - 1;
			while(l < r){
				int mid = l + r >> 1;
				vector < int > tmp = ask(mid);
				if(tmp[0] + tmp[1] == 0){
					return mid;
				}
				if(tmp[0] + tmp[1] < mx){
					r = mid;
				}
				else{
					if(res[1] - tmp[1] > 0){
						r = mid - 1;
					}
					else{
						l = mid + 1;
					}
				}
			}
			res = ask(l);
			if(res[0] + res[1] == 0){
				return l;
			}
			i = l + 1;
		}
		else{
			++i;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int mid = l + r >> 1;
      |               ~~^~~
prize.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
   50 | }
      | ^

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