Submission #340826

#	Time	Username	Problem	Language	Result	Execution time	Memory
340826		pggp	The Big Prize (IOI17_prize)	C++14	97.63 / 100	67 ms	2860 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

int higher[200000];
int left_h[200000];
int right_h[200000];
int N;

void search(int l, int r){
	//cout << l << " " << r << endl;
	if(r < l + 2){
		return;
	}
	if(left_h[l] == left_h[r]){
		return;
	}
	int mid = (r + l) / 2;
	vector < int > a = ask(mid);
	higher[mid] = a[0] + a[1];
	left_h[mid] = a[0];
	right_h[mid] = a[1];
	if(a[0] + a[1] < 2 * sqrt(N)){
		search(l, mid);
		search(mid, r);
	}
	else{
		for (int i = mid - 1; i > l; --i)
		{
			vector < int > a1 = ask(i);
			higher[i] = a1[0] + a1[1];
			left_h[i] = a1[0];
			right_h[i] = a1[1];
			if(a1[0] + a1[1] < 2 * sqrt(N)){
				search(l, i);
			}
		}
		for (int i = mid + 1; i < r; ++i)
		{
			vector < int > a1 = ask(i);
			higher[i] = a1[0] + a1[1];
			left_h[i] = a1[0];
			right_h[i] = a1[1];
			if(a1[0] + a1[1] < 2 * sqrt(N)){
				search(l, i);
			}
		}
	}
}

int find_best(int n){
	N = n;
	for (int i = 0; i < 200000; ++i)
	{
		higher[i] = -1;
	}
	int l_min;
	for (int i = 0; i < n; ++i)
	{
		vector < int > a = ask(i);
		higher[i] = a[0] + a[1];
		left_h[i] = a[0];
		right_h[i] = a[1];
		if(a[0] + a[1] < 2 * sqrt(n)){
			l_min = i;
			break;
		}
	}


	int r_max;
	for (int i = n - 1; i >= 0; --i)
	{
		vector < int > a = ask(i);
		higher[i] = a[0] + a[1];
		left_h[i] = a[0];
		right_h[i] = a[1];
		if(a[0] + a[1] < 2 * sqrt(n)){
			r_max = i;
			break;
		}
	}

	search(l_min, r_max);

	for (int i = 0; i < n; ++i)
	{
			if(higher[i] == 0){
			return i;
		}
	}

}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:94:1: warning: control reaches end of non-void function [-Wreturn-type]
   94 | }
      | ^
prize.cpp:85:8: warning: 'l_min' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |  search(l_min, r_max);
      |  ~~~~~~^~~~~~~~~~~~~~
prize.cpp:85:8: warning: 'r_max' may be used uninitialized in this function [-Wmaybe-uninitialized]

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