Submission #652490

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

books

#include <bits/stdc++.h>

#include "books.h"
typedef long long ll;
using namespace std;

#define MAX 101010
ll arr[MAX];

ll query(int x) {
	if (arr[x]) return arr[x];
	return arr[x] = skim(x);
}

void solve(int N, int K, long long A, int S) {
	int i;
	ll sum = 0;
	for (i = 1; i < K; i++) sum += query(i);
	int l, r;
	l = K;
	r = N + 1;
	while (r - l > 1) {
		int mid = (l + r) / 2;
		if (query(mid) + sum > 2ll * A) r = mid;
		else l = mid;
	}
	if (sum + query(l) > 2ll * A) {
		impossible();
		return;
	}
	if (sum + query(l) >= A) {
		vector<int> v;
		int i;
		for (i = 1; i < K; i++) v.push_back(i);
		v.push_back(l);
		answer(v);
	}
	for (i = K; i >= 0; i--) {
		int j;
		ll sum = 0;
		for (j = 1; j <= i; j++) sum += query(j);
		for (j = 1; j <= K - i; j++) sum += query(l - j + 1);
		if (A <= sum && sum <= 2 * A) {
			vector<int> v;
			for (j = 1; j <= i; j++) v.push_back(j);
			for (j = 1; j <= K - i; j++) v.push_back(l - j + 1);
			answer(v);
			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