Submission #1211524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211524		vyaduct	The Big Prize (IOI17_prize)	C++20	20 / 100	24 ms	408 KiB

prize

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

#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector

int find_best(int n){
	ll mx=0;
	int ENOUGH = 467;
	if (n < ENOUGH){
		for (int i=0;i<n;i++){
			vt<int> res = ask(i);
      // cout << res[0] << " " << res[1] << endl;
			if (res[0] == 0 && res[1] == 0){
				return i;
			}
		}
	}
	int cur = 0;
	for (int i=0;i<ENOUGH;i++){
		vt<int> res = ask(i);
    if (res[0] == 0 && res[1] == 0) return i;
		cur = max(cur, res[0]+res[1]);
	}
  // cout << "I found out the max is " << cur << endl;

	int start = 0;
  int last=0;
	while(start < n){
		int l=start,r=n-1;
		while(l<r){
			int m = l + (r-l+1)/2;
			vt<int> res = ask(m);
      if (res[0] == 0 && res[1] == 0) return m;
      // cout << "im asking " << m << endl; 
      // cout << "i got " << res[0] << " " << res[1] << endl;
			if (res[0] == last && res[0]+res[1]==cur){
        // cout << "i decided my left is cool" << endl;
				l = m;
			} else {
				r = m-1;
        // cout << "i decided my left isn't cool" << endl;
			}
		}
		l++;
    // cout << "wondering in the wild : " <<  l << endl;
		while(l<n){
			vt<int> a = ask(l);
			if (a[0]+a[1] == cur) break; // lolipop, break
			if (a[0]+a[1] == 0) return l;
			else l++;
		}
    // cout << "after wondering i got to " << l << endl;
    if (l != n) last = ask(l)[0];
    start = l;
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

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