제출 #292985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
292985		luciocf	The Big Prize (IOI17_prize)	C++14	90 / 100	112 ms	1920 KiB

prize

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

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5+10;

pii val[maxn];

pii get(int i)
{
	vector<int> v = ask(i);

	return {v[0], v[1]};
}

int find_best(int n)
{
	for (int i = 0; i < n; i++)
		val[i] = {-1, -1};

	int ind = 0;
	int qtd = 0;

	for (int i = 0; i < min(n, 500); i++)
	{
		int v = get(i).ff+get(i).ss;

		if (v == 0) return i;

		if (v >= qtd)
			qtd = v, ind = i;
	}

	int ant = ind;

	val[ind] = get(ind);

	for (int i = 1; i <= 500; i++)
	{
		int ini = ant+1, fim = n-1, ans;

		while (ini <= fim)
		{
			int mid = (ini+fim)/2;

			if (val[mid].ff == -1) val[mid] = get(mid);

			if (val[mid].ff+val[mid].ss != qtd)
			{
				if (val[mid].ff+val[mid].ss == 0) return mid;

				ans = mid, fim = mid-1;
			}
			else if (val[mid].ff-val[ind].ff-(i-1) > 0) fim = mid-1;
			else ini = mid+1;
		}

		ant = ans;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:66:1: warning: control reaches end of non-void function [-Wreturn-type]
   66 | }
      | ^
prize.cpp:46:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |   int ini = ant+1, fim = n-1, ans;
      |       ^~~

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