Submission #428308

#	Time	Username	Problem	Language	Result	Execution time	Memory
428308		NachoLibre	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	4 ms	1096 KiB

books

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef long long ll;
#ifndef wambule
#include "books.h"
#else
vector<ll> _X;
ll skim(int i) {
	return _X[i - 1];
}
void answer(vint v) {
	for(int i = 0; i < v.size(); ++i) {
		cout << v[i] << " ";
	}
	cout << endl;
}
void impossible() {
	cout << "-__-" << endl;
}
#endif

void solve(int n, int k, ll a, int) {
	vector<ll> x(n + 1);
	ll tj = 0;
	for(int i = 1; i <= k; ++i) {
		x[i] = skim(i);
		tj += x[i];
	}
	if(tj > a * 2) {
		impossible();
		return;
	}
	if(tj >= a) {
		vint dr;
		for(int i = 1; i <= k; ++i) {
			dr.push_back(i);
		}
		answer(dr);
		return;
	}
	int l = 1, r = n;
	if(skim(n) < a) l = r = n + 1;
	while(l < r) {
		int m = l + r >> 1;
		if(skim(m) >= a) r = m;
		else l = m + 1;
	}
	for(int i = l - k; i < l; ++i) {
		x[i] = skim(i);
	}
	if(l != n + 1) {
		x[l] = skim(l);
		tj = x[l];
		for(int i = 1; i < k; ++i) {
			tj += x[i];
		}
		if(tj <= a * 2) {
			vint dr;
			for(int i = 1; i < k; ++i) {
				dr.push_back(i);
			}
			dr.push_back(l);
			answer(dr);
			return;
		}
	}
	tj = 0;
	for(int i = 1; i <= k; ++i) {
		tj += x[i];
	}
	int c = k;
	while(tj < a && c > 0) {
		tj += x[l - k + c - 1] - x[c]; --c;
	}
	if(tj >= a) {
		vint dr;
		for(int i = 1; i <= c; ++i) {
			dr.push_back(i);
		}
		for(int i = l - k + c; i < l; ++i) {
			dr.push_back(i);
		}
		answer(dr);
		return;
	}
	impossible();
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	_X = {1, 2, 3, 4, 5, 11};
	int k = 4;
	ll a = 11;
	solve(_X.size(), k, a, 0);
	return 0;
}
#endif

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, ll, int)':
books.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int m = l + r >> 1;
      |           ~~^~~

• 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