Submission #411318

#	Time	Username	Problem	Language	Result	Execution time	Memory
411318		ronnith	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	3 ms	1096 KiB

books

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

using namespace std;

void solve(int N, int K, long long A, int S) {
	int lx = 1, rx = N;
	vector<int64_t> val(N + 1, -1);
	int pos = N + 1;
	while (lx <= rx) {
		int g = lx + (rx - lx) / 2;
		val[g] = skim(g);
		if (val[g] < A) {
			lx = g + 1;
		} else {
			pos = g;
			rx = g - 1;
		}
	}

	for (int i = 1;i <= K;i ++)
		val[i] = skim(i);
	for (int i = pos - 1;i >= max(pos - K, 1);i --)
		val[i] = skim(i);

	if (pos < K) {
		impossible();
		return;
	}

	if (pos >= K && pos != N + 1) {
		int64_t sm = 0;
		vector<int> ans;
		for (int i = 1;i <= K - 1;i ++) {
			sm += val[i];
			ans.push_back(i);
		}
		ans.push_back(pos);
		sm += val[pos];

		if (sm >= A && sm <= 2 * A) {
			answer(ans);
			return;
		}
	}

	vector<int> ind;
	vector<int64_t> values;
	ind.push_back(-1);
	values.push_back(-1);
	for (int i = 1;i <= K;i ++) {
		values.push_back(val[i]);
		ind.push_back(i);
	}

	for (int i = max(pos - K, K + 1);i < pos;i ++) {
		values.push_back(val[i]);
		ind.push_back(i);
	}
	
	for (int i = 1;i <= K + 1;i ++) {
		if ((int)values.size() - i >= K) {
			int64_t sm = 0;
			vector<int> ans;
			for (int j = 0;j < K;j ++) {
				sm += values[i + j];
				ans.push_back(ind[i + j]);
			}

			if (sm >= A && sm <= 2 * A) {
				answer(ans);
				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