Submission #1201677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201677		IBory	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	1188 KiB

books

#include <bits/stdc++.h>
#include "books.h"
typedef long long ll;
using namespace std;

const int MAX = 100007;
ll X[MAX];

ll Skim(int p) {
	if (X[p]) return X[p];
	return X[p] = skim(p);
}

void solve(int N, int K, ll A, int S) {
	memset(X, 0, 8 * (N + 1));

	ll base = 0;
	for (int i = 1; i < K; ++i) base += Skim(i);

	int L = K, R = N + 1;
	while (L + 1 < R) {
		int mid = (L + R) >> 1;
		(A * 2 < base + Skim(mid) ? R : L) = mid;
	}

	vector<int> ans(K);
	iota(ans.begin(), ans.end(), 1);
	if (A * 2 < base + Skim(L)) impossible();
	if (A <= base + skim(L)) {
		ans[K - 1] = L;
		answer(ans);
		return;
	}

	base += Skim(K);
	for (int i = K; i > 0; --i) {
		int r = L - (K - i);
		base += Skim(r) - Skim(i);
		ans[i - 1] = r;
		if (A <= base && base <= A * 2) {
			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