Submission #525906

#	Time	Username	Problem	Language	Result	Execution time	Memory
525906		Qingyu	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1092 KiB

books

#include <bits/stdc++.h>

#include "books.h"

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.
//

void solve(int N, int K, long long A, int S) {
	auto ok = [&](long long x) -> bool {
		return A <= x && x <= 2 * A;
	};
	vector<long long> X(N + 1, -1);
	auto get = [&](int k) -> long long {
		if (X[k] == -1) X[k] = skim(k);
		return X[k];
	};
	long long total = 0;
	for (int i = 1; i <= K; ++i) {
		total += get(i);	
	}
	if (total > 2 * A) {
		impossible();
		return;
	}
	if (total >= A) {
		vector<int> v;
		for (int i = 1; i <= K; ++i) v.push_back(i);
		answer(v);
		return;
	}
	int l = K, r = N, ans = -1;
	while (l <= r) {
		const int mid = l + r >> 1;
		if (X[mid] == -1) X[mid] = skim(mid);
		if (X[mid] < A) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	if (ans < N) {
		total = 0;
		for (int i = 1; i < K; ++i) total += get(i);
		total += get(ans + 1);
		assert(total >= A);
		if (total <= 2 * A) {
			vector<int> v;
			for (int i = 1; i < K; ++i) v.push_back(i);
			v.push_back(ans + 1);
			answer(v);
			return;
		}
	}
	if (ans - K + 1 <= K) {
		for (int j = K + 1; j <= ans; ++j)
			X[j] = skim(j);
		auto Y = X;
		for (int i = 1; i <= ans; ++i) Y[i] += Y[i - 1];
		for (int i = K; i <= ans; ++i)
			if (ok(Y[i] - Y[i - K])) {
				vector<int> v;
				for (int j = i - K + 1; j <= i; ++j)
					v.push_back(j);
				answer(v);
				return;
			}
		impossible();
		return;
	}
	for (int i = ans - K + 1; i <= ans; ++i)
		if (X[i] == -1)
			X[i] = skim(i);
	total = 0;
	for (int i = 1; i <= K; ++i) total += X[i];

	for (int j = 1; j <= K; ++j) {
		total -= X[j];
		total += X[ans - K + j];
		if (ok(total)) {
			vector<int> v;
			for (int t = j + 1; t <= K; ++t) v.push_back(t);
			for (int t = 1; t <= j; ++t)
				v.push_back(ans - K + t);
			answer(v);
			return;
		}
	}
	impossible();
	return;
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:41:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   const int mid = 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