Submission #441737

#	Time	Username	Problem	Language	Result	Execution time	Memory
441737		8e7	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	1 ms	328 KiB

books

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <assert.h>
using namespace std;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) { cout << a << " ";debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << (*l) << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#include "books.h"
const ll inf = 1LL<<60;
ll save[maxn];
bool found[maxn];
int tot;
ll query(int ind) {
	if (ind > tot || ind < 0) return inf;
	if (found[ind]) return save[ind];
	found[ind] = 1;
	return save[ind] = skim(ind);
}
void solve(int N, int K, long long A, int S) {
	vector<int> ret;
	tot = N;
	int low = 0, up = N + 1;
	while (up > low + 1) {
		int mid = (low + up) / 2;
		if (query(mid)>= A / K) up = mid;
		else low = mid;	
	}
	int ind = up, lef = ind, rig = ind, big = N + 1;
	ll sum = 0;
	if (query(ind) >= A) {
		big = ind;
	} else {
		for (int i = 0;i < K;i++) {
			ll val = query(ind + i);
			if (val >= A) {
				big = ind + i;
				break;
			}
			sum += val;
			rig = ind + i;
			if (sum >= A) {
				break;
			}
		}
		//debug(rig, big);
		while (rig - lef + 1 < K) {
			lef--;
			if (lef <= 0) {
				lef++;
				while (rig - lef + 1 < K) {
					rig++;
					ll val = query(rig);
					sum += val;
				}
				break;
			}
			ll val = query(lef);
			sum += val;
			if (sum > 2 * A) sum -= query(rig), rig--;
		}
		if (sum >= A && sum <= 2 * A) {
			for (int i = lef;i <= rig;i++) ret.push_back(i);
			answer(ret);
			return;
		}
	}
	if (big > N) {
		assert(query(N) < A);
		impossible();
		return;
	} else if (big < K) {
		impossible();
		return;
	}
	sum = query(big);
	ret.push_back(big);
	for (int i = 1;i < K;i++) sum += query(i), ret.push_back(i);
	if (sum <= 2 * A) {
		answer(ret);
	} else {
		impossible();
	}
}
/*
15 3 42 15
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
 
8 3 49 8
1 2 3 4 40 87 98 99
  */

• 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