Submission #537296

#	Time	Username	Problem	Language	Result	Execution time	Memory
537296		skittles1412	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	432 KiB

books

#include "bits/extc++.h"
#include "books.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 1e5 + 5;

long arr[maxn];

long query(int i) {
	if (arr[i]) {
		return arr[i];
	}
	return arr[i] = skim(i + 1);
}

void solve(int n, int k, ll av, int s) {
	int l = 0, r = n;
	while (l < r) {
		int mid = (l + r) / 2;
		if (query(mid) >= av) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	auto go = [&](int rb) -> void {
		for (int i = 0; i <= k; i++) {
			vector<int> vals;
			for (int j = 0; j < i; j++) {
				vals.push_back(j);
			}
			for (int j = 0; j < k - i; j++) {
				vals.push_back(rb - j);
			}
			sort(begin(vals), end(vals));
			if (unique(begin(vals), end(vals)) != vals.end()) {
				continue;
			}
			long sum = 0;
			for (auto& a : vals) {
				if (0 <= a && a < n) {
					sum += query(a);
				} else {
					goto loop;
				}
			}
			if (av <= sum && sum <= 2 * av) {
				for (auto& a : vals) {
					a++;
				}
				answer(vals);
			}
			loop:;
		}
	};
	go(l);
	go(l - 1);
	impossible();
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20