Submission #441405

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

books

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <set>
//#include <ext/pb_ds/assoc_contatiner.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
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) 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;	
	ll big = 0;
	while (low < up - 1) {
		int mid = (low + up) / 2;
		if (query(mid) >= A) up = mid, big = query(mid);
		else low = mid;
	}
	if (up < K) {
		impossible();
		return;
	}
	//debug(up);
	if (up <= N) {
		ll c1 = big;
		for (int i = 1;i < K;i++) c1 += query(i); 
		if (c1 <= 2 * A) {
			for (int i = 1;i < K;i++) ret.push_back(i);
			ret.push_back(up);	
			answer(ret);
			return;
		}
	}
	low = 0, up = min(up - K + 2, N - K + 2);
	//debug(low, up);
	while (up > low + 1) {
		//debug(low, up);
		int mid = (low + up) / 2;
		ll sum = 0;
		for (int i = mid;i < mid + K;i++) {
			sum += query(i);
			if (sum >= A) break;
		}
		if (sum >= A) up = mid;
		else low = mid;
	}
	ll val = 0;	
	for (int i = up;i < up + K;i++) ret.push_back(i), val += query(i);
	if (val >= A && val <= 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 7 14 40 97 98 99
  */

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20