Submission #548086

#	Time	Username	Problem	Language	Result	Execution time	Memory
548086		jhwest2	The Big Prize (IOI17_prize)	C++17	20 / 100	78 ms	2724 KiB

prize

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

const int M = 2e5 + 10;
pair<int, int> A[M];

pair<int, int> doAsk(int i) {
	if (A[i].first != -1) {
		return A[i];
	}
	vector<int> r = ask(i);
	return A[i] = { r[0], r[1] };
}
void search(vector<int> &I, vector<int> &J, int l, int r, int v, int lo, int hi) {
	if (lo == hi) {
		J.push_back(I[lo]); return;
	}
	int m = lo + hi >> 1;
	auto [vl, vr] = doAsk(I[m]);

	int c = 0, off = 0, ll = m, rr = m;
	while (vl + vr != v) {
		J.push_back(I[m + off]);
		c += 1;
		if (off <= 0) {
			off = -off + 1;
			rr = m + off;
		}
		else {
			off = -off;
			ll = m + off;
		}

		if (m + off < lo || m + off > hi) {
			return;
		}
		auto [nl, nr] = doAsk(I[m + off]);
		vl = nl; vr = nr;
	}

	if (off <= 0) {
		if (l != vl) search(I, J, l, vr, v, lo, m + off);
		if (r + c != vr) search(I, J, vl + c, r, v, m - off + 1, hi);		
	}
	else {
		if (l + c != vl) search(I, J, l, vr + c, v, lo, m - off);
		if (r != vr) search(I, J, vl, r, v, m + off, hi);
	}
}
int find_best(int n) {
	for (int i = 0; i < n; i++) {
		A[i].first = -1;
	}
	vector<int> I(n), J;
	for (int i = 0; i < n; i++) {
		I[i] = i;
	}
	for (int i = 0; i < 5; i++) {
		int x = 0;
		for (int j = 0; j < min((int)I.size(), (int)sqrt(I.size()) + 20); j++) {
			auto [a, b] = doAsk(I[j]);
			x = max(x, a + b);
		}
		search(I, J, 0, 0, x, 0, (int)I.size() - 1);

		I = J; J.clear();
		sort(I.begin(), I.end());
	}
	return I[0];
}

Compilation message (stderr)

prize.cpp: In function 'void search(std::vector<int>&, std::vector<int>&, int, int, int, int, int)':
prize.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |  int m = lo + hi >> 1;
      |          ~~~^~~~
prize.cpp:22:22: warning: variable 'll' set but not used [-Wunused-but-set-variable]
   22 |  int c = 0, off = 0, ll = m, rr = m;
      |                      ^~
prize.cpp:22:30: warning: variable 'rr' set but not used [-Wunused-but-set-variable]
   22 |  int c = 0, off = 0, ll = m, rr = m;
      |                              ^~

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