Submission #441411

#TimeUsernameProblemLanguageResultExecution timeMemory
4414118e7A Difficult(y) Choice (BOI21_books)C++14
Compilation error
0 ms0 KiB
//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<<55;
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, lim = N + 1;	
	ll big = 0;
	while (low < up - 1) {
		int mid = (low + up) / 2;
		ll val = query(mid);
		if (val * K > 2 * A) lim = min(lim, mid);
		if (val >= A) up = mid, big = val;
		else low = mid;
	}
	if (up < K) {
		impossible();
		return;
	}
	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(lim, min(up - K + 2, N - K + 2));
	assert(up > 1);
	while (up > low + 1) {
		int mid = (low + up) / 2;
		ll sum = 0;
		for (int i = mid;i < mid + K;i++) {
			ll val = query(i);
			sum += val;
			if (sum >= A || sum + (ll)(mid + K - i - 1) * val >= A) {
				sum = A + 1;
				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
  */

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:62:2: error: 'assert' was not declared in this scope
   62 |  assert(up > 1);
      |  ^~~~~~
books.cpp:25:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
   24 | #include "books.h"
  +++ |+#include <cassert>
   25 | const ll inf = 1LL<<55;