Submission #995012

#	Time	Username	Problem	Language	Result	Execution time	Memory
995012		caterpillow	The Big Prize (IOI17_prize)	C++17	99.72 / 100	42 ms	1988 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
	os << "{"; 
	int g = size(o); 
	for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
	os << "}";
	return os;
}

void _print() {
	cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
	cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define cerr(x...) cerr << #x << " = "; _print(x);
#else
#define cerr(x...)
#define cerr if (0) std::cerr
#endif

/*

there are at most O(sqrt n) different types of prizes
constraints suggest 2 * sqrt(n) * log2(n)
we can differentiate levels of boxes based on sum of query results
there are at most sqrt non-complete-trash prizes
if we can isolate each "level" of prizes, we can work our way up to the top

consider only the worst type of prize
there are at most sqrt(n) connected components of prizes better than this
we can bsearch for these components

to find a l point, move it right while the # of better prizes to its left doesnt change
to find a r point, move it right while the # of better prizes to its right doesnt change 
take these points, and squish the new array such that we only consider these indices now

do this recursively unitl we end up with an array of length 1

*/

map<int, pi> memo;
pi _query(int i) {
	if (memo.count(i)) return memo[i];
	vt<int> res = ask(i);
	return memo[i] = {res[0], res[1]};
}

struct Array {
	vt<int> actual;
	void pb(int v) {
		actual.pb(v);
	}
	pi query(int i) {
		if (i < 0) return {0, 0};
		return _query(actual[i]);
	}
	int operator[](int i) {
		return actual[i];
	}
	int sz() {
		return size(actual);
	}
};

/*

to find a l point, move it right while the # of better prizes to its left doesnt change (so query res is equal or less than original)
take these points, and squish the new array such that we only consider these indices now

*/

void solve(Array& a, int tot) {
	vt<pi> rngs; // inc, exc
	int n = a.sz();
	int l = -1, r;
	while (l < n) {
		int lo = -1, hi = n;
		int bruh = a.query(l).f;
		if (bruh > tot) {
			solve(a, bruh);
			return;
		}
		while (hi - lo > 1) {
			int m = (lo + hi) / 2;
			auto [x, y] = a.query(m);
			if (x + y > tot) {
				solve(a, x + y);
				return;
			}
			if (m <= l || (x + y == tot && x <= bruh)) lo = m;
			else hi = m;
		}
		l = lo + 1;

		if (l == n) break; // reached end of arr
		int r = l + 1; // exc
		while (r < n) {
			auto [lhs, rhs] = a.query(r);
			if (lhs + rhs > tot) {
				solve(a, lhs + rhs);
				return;
			}
			if (lhs + rhs == tot) break;
			else r++;
		}
		rngs.pb({l, r});
		l = r;
	}
	Array narr;
	for (auto [l, r] : rngs) {
		FOR (i, l, r) {
			narr.pb(a[i]);
		}
	}
	a = narr;
}

int find_best(int _n) {
	Array arr;
	int n = _n;
	F0R (i, n) {
		arr.pb(i);
	}

	while (arr.sz() > 1) {
		solve(arr, arr.query(0).f + arr.query(0).s);
	}
	auto [l, r] = _query(arr[0]);
	assert(l + r == 0);
	return arr[0];
}

Compilation message (stderr)

prize.cpp:44: warning: "cerr" redefined
   44 | #define cerr if (0) std::cerr
      | 
prize.cpp:43: note: this is the location of the previous definition
   43 | #define cerr(x...)
      | 
prize.cpp: In function 'void solve(Array&, int)':
prize.cpp:101:14: warning: unused variable 'r' [-Wunused-variable]
  101 |  int l = -1, r;
      |              ^

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