Submission #1260714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260714		thewizardman	The Big Prize (IOI17_prize)	C++20	0 / 100	1068 ms	5120 KiB

prize

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

int mx, first;
vector<int> v[200000];

inline bool a(int i) {
	if (v[i].empty()) v[i] = ask(i);
	return (v[i][0] + v[i][1] == mx);
}

void skibidi(int l, int r) {
	int mid = (l + r) >> 1;
	int rr = mid, ll = mid;
	bool f = a(mid);
	while (rr < r && !f) f = a(++rr);
	while (ll > l && !f) f = a(--ll);
	if (f && v[ll][0] > v[l][0]) skibidi(l, ll);
	if (f && v[rr][1] > v[r][1]) skibidi(rr, r);
}

int find_best(int n) {
	for (int i = 0; i < min(n, 474); i++) {
		a(i);
		if (v[i][0] + v[i][1] > mx) first = i, mx = v[i][0] + v[i][1];
	}
	a(n-1);
	skibidi(first, n-1);
	for (int i = 0; i < n; i++) if (v[i].size()) if (v[i][0] + v[i][1] == 0) return i;
}

Compilation message (stderr)

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

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