Submission #165612

#	Time	Username	Problem	Language	Result	Execution time	Memory
165612		johutha	The Big Prize (IOI17_prize)	C++14	98.83 / 100	92 ms	512 KiB

prize

#include "prize.h"
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

struct segment
{
	int l, r;
	int cnt_r;
	int cnt_l;
	int cnt_ins = -1;
};

int find_best(int n)
{
	queue<segment> q;

	segment s1;
	s1.l = 0;
	s1.r = n;
	s1.cnt_l = 0;
	s1.cnt_r = 0;
	q.push(s1);

	while (!q.empty())
	{
		segment curr = q.front();
		q.pop();
		int mid = (curr.l + curr.r) / 2;
		bool found = false;
		for (int i = mid; i < min(mid + (int)ceil(sqrt(n)) + 1, curr.r); i++)
		{
			auto r = ask(i);
			if (r[0] + r[1] == 0) return i;
			if (r[0] + r[1] < n / 2)
			{
				found = true;
				segment sl = curr;
				sl.r = mid;
				sl.cnt_ins = r[0] - curr.cnt_l;
				sl.cnt_r = r[1];
				segment sr = curr;
				sr.l = mid + 1;
				sr.cnt_ins = r[1] - curr.cnt_r;
				sr.cnt_l = r[0];
				if (sl.cnt_ins != 0) q.push(sl);
				if (sr.cnt_ins != 0) q.push(sr);
				break;
			}
		}
		if (!found)
		{
			segment ns = curr;
			ns.r = mid;
			ns.cnt_r += curr.r - mid;
			ns.cnt_ins -= curr.r - mid;
			if (ns.cnt_ins != 0) q.push(ns);
		}
	}
}

Compilation message (stderr)

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

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