Submission #409019

#	Time	Username	Problem	Language	Result	Execution time	Memory
409019		Kevin_Zhang_TW	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	4 ms	1096 KiB

books

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
void debug(auto l, auto r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "books.h"

const int MAX_N = 300010;

using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//
// ll skim(int index);
// void answer(vector<int> choose);
// void impossible();

void solve(int N, int K, long long A, int S) {

	vector<ll> cache(N+1, -1);

	auto qry = [&](int id) {
		assert(id >= 1 && id <= N);
		if (cache[id] == -1) cache[id] = skim(id);
		return cache[id];
	};

	{
//		for (int i = 1;i <= N;++i)
//			if (qry(i) > A) N = i;
		int l = 1, r = N, m;
		while (l < r) {
			m = l + r >> 1;
			if (qry(m) > A)
				r = m;
			else l = m+1;
		}
		N = l;
	};

	if (N < K) impossible();

	if (qry(N) > A) {
		vector<int> pk {N};
		ll sum = qry(N);
		for (int i = 1;i < K;++i) {
			sum += qry(i);
			pk.pb(i);
		}
		if (sum <= A + A) answer(pk);
		--N;
	};

	if (N < K) impossible();

	assert(qry(N) <= A);

	ll sum = 0;
	auto valid = [&]() { return sum >= A && sum <= A + A; };
	vector<int> pk;
	for (int i = N-K+1;i <= N;++i) {
		pk.pb(i);
		sum += qry(i);
	}

	if (sum < A) impossible();
	if (sum <= A + A) answer(pk);

	for (int i = 0;i < K;++i) {
		int old = pk[i];
		sum -= qry(pk[i]);
		sum += qry(pk[i] = i+1);
		if (sum > A + A) continue;
		if (sum >= A) answer(pk);
		sum -= qry(i+1);
		int l = i+2, r = old-1, m;
		while (l < r) {
			m = l + r >> 1;
			if (sum + qry(m+1) > A + A)
				r = m;
			else l = m+1;
		}
		pk[i] = l;
		sum += qry(l);
		assert(valid());
		answer(pk);
	}

	impossible();
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:50:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |    m = l + r >> 1;
      |        ~~^~~
books.cpp:95:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |    m = l + r >> 1;
      |        ~~^~~

• 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