Submission #1260705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260705		thewizardman	The Big Prize (IOI17_prize)	C++20	0 / 100	1069 ms	5124 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 nl, int nr) {
	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] > nl) skibidi(l, ll, nl, v[ll][1]);
	if (f && v[rr][1] > nr) skibidi(rr, r, v[rr][0], nr);
}

int find_best(int n) {
	for (int i = 0; i < min(n, 474); i++) {
		v[i] = ask(i);
		if (v[i][0] + v[i][1] > mx) first = i, mx = v[i][0] + v[i][1];
	}
	skibidi(first, n-1, first, 0);
	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:30:1: warning: control reaches end of non-void function [-Wreturn-type]
   30 | }
      | ^

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