Submission #544757

#	Time	Username	Problem	Language	Result	Execution time	Memory
544757		rainboy	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	404 KiB

books

#include "books.h"
 
using namespace std;
 
const int N = 100000;
 
long long aa[N + 1];
 
void solve(int n, int k, long long a, int s) {
	vector<int> ii(k);
	int i, lower, upper;
	long long sum;
 
	lower = 1, upper = n + 1;
	while (upper - lower > 1) {
		i = (lower + upper) / 2;
		if ((aa[i] = skim(i)) >= a)
			upper = i;
		else
			lower = i;
	}
	if (upper < k) {
		impossible();
		return;
	}
	for (i = 1; i <= k; i++)
		aa[i] = skim(i);
	if (upper <= n) {
		sum = aa[upper];
		for (i = 1; i < k; i++)
			sum += aa[i];
		if (sum <= a * 2) {
			for (i = 1; i < k; i++)
				ii[i - 1] = i;
			ii[k - 1] = upper;
			answer(ii);
			return;
		}
		if ((n = upper - 1) < k) {
			impossible();
			return;
		}
	}
	sum = 0;
	for (i = 1; i <= k; i++)
		ii[i - 1] = i, sum += aa[i];
	if (sum > a * 2) {
		impossible();
		return;
	}
	if (sum >= a) {
		answer(ii);
		return;
	}
	for (i = k; i >= 1; i--) {
		ii[i - 1] = n - (k - i), sum += skim(n - (k - i)) - aa[i];
		if (sum >= a) {
			answer(ii);
			return;
		}
	}
	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