Submission #548094

#	Time	Username	Problem	Language	Result	Execution time	Memory
548094		jhwest2	The Big Prize (IOI17_prize)	C++17	100 / 100	46 ms	2728 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#pragma optimize
using namespace std;

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

inline pair<int, int> doAsk(int i) {
	if (A[i].first != -1) {
		return A[i];
	}
	r = ask(i);
	return A[i] = { r[0], r[1] };
}


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;
	}
	while (I.size() != 1) {
		int x = 0, p = 0;
		Q[p++] = { 0, 0, 0, (int)I.size() - 1 };

		for (int j = 0; j < min((int)I.size(), (int)sqrt(I.size()) + 26); j++) {
			auto [l, r, lo, hi] = Q[--p];
			auto [a, b] = doAsk(I[lo + hi >> 1]);
			x = max(x, a + b);

			Q[p++] = { 0, 0, lo, lo + hi >> 1 };
			Q[p++] = { 0, 0, 1 + (lo + hi >> 1), hi };
		}
		p = 0;
		Q[p++] = { 0, 0, 0, (int)I.size() - 1 };

		while (p != 0) {
			auto [l, r, lo, hi] = Q[--p];

			if (lo == hi) {
				J.push_back(I[lo]);
				continue;
			}
			int m = lo + hi >> 1;
			auto [vl, vr] = doAsk(I[m]);

			int c = 0, off = 0, ll = m, rr = m;
			while (vl + vr != x) {
				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) {
					break;
				}
				auto [nl, nr] = doAsk(I[m + off]);
				vl = nl; vr = nr;
			}
			if (m + off < lo || m + off > hi) {
				continue;
			}

			if (off <= 0) {
				if (l + vr != x) Q[p++] = { l, vr, lo, m + off };
				if (vl + c + r != x) Q[p++] = { vl + c, r, m - off + 1, hi };
			}
			else {
				if (l + vr + c != x) Q[p++] = { l, vr + c, lo, m - off };
				if (vl + r != x) Q[p++] = { vl, r, m + off, hi };
			}
		}
		I = J; J.clear();
		sort(I.begin(), I.end());
	}
	return I[0];
}

Compilation message (stderr)

prize.cpp:7: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    7 | #pragma optimize
      | 
prize.cpp: In function 'int find_best(int)':
prize.cpp:38:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |    auto [a, b] = doAsk(I[lo + hi >> 1]);
      |                          ~~~^~~~
prize.cpp:41:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |    Q[p++] = { 0, 0, lo, lo + hi >> 1 };
      |                         ~~~^~~~
prize.cpp:42:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |    Q[p++] = { 0, 0, 1 + (lo + hi >> 1), hi };
      |                          ~~~^~~~
prize.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |    int m = lo + hi >> 1;
      |            ~~~^~~~
prize.cpp:57:24: warning: variable 'll' set but not used [-Wunused-but-set-variable]
   57 |    int c = 0, off = 0, ll = m, rr = m;
      |                        ^~
prize.cpp:57:32: warning: variable 'rr' set but not used [-Wunused-but-set-variable]
   57 |    int c = 0, off = 0, ll = m, rr = m;
      |                                ^~

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