Submission #906262

#	Time	Username	Problem	Language	Result	Execution time	Memory
906262		MinaRagy06	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	1380 KiB

books

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#else
#ifdef DEBUG
#include "grader2.cpp"
#endif
#endif
#include "books.h"
#define ll long long
using namespace std;

ll b[100'005];
ll ask(int i) {
	if (~b[i]) return b[i];
	return b[i] = skim(i + 1);
}
void solve(int n, int k, ll a, int Q) {
	memset(b, -1, sizeof b);
	ll s = 0;
	for (int i = 0; i < k; i++) {
		s += ask(i);
	}
	if (s > 2 * a) {
		impossible();
		return;
	}
	if (a <= s && s <= 2 * a) {
		vector<int> ans;
		for (int i = 0; i < k; i++) {
			ans.push_back(i + 1);
		}
		answer(ans);
		return;
	}
	s -= ask(k - 1);
	int l = k - 1, r = n - 1;
	while (l <= r) {
		int md = ((l + r) >> 1);
		if (s + ask(md) <= 2 * a) {
			l = md + 1;
		} else {
			r = md - 1;
		}
	}
	if (r < k - 1) {
		impossible();
	}
	s += ask(r);
	int cur = 0;
	while (s < a) {
		s -= ask(cur);
		cur++;
		if (r - cur <= k - 2 || cur > k - 1) impossible();
		s += ask(r - cur);
	}
	vector<int> ans;
	for (int i = cur; i < k - 1; i++) {
		ans.push_back(i + 1);
	}
	for (int i = r; i >= r - cur; i--) {
		ans.push_back(i + 1);
	}
	answer(ans);
}

• 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