Submission #773355

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;

void solve(int N, int K, ll A, int S) {
	ll a[N+1];
	memset(a, -1, sizeof(a));
	
	auto ask = [&](int i) {
		return a[i] = a[i] < 0 ? skim(i) : a[i];
	};
	
	ll sum = 0;
	for (int i = 1; i < K; i++) {
		sum += ask(i);
	}
	
	if (sum >= A) {
		if (sum + ask(K) > A+A) {
			impossible();
		}
		vector<int> ans(K);
		iota(ans.begin(), ans.end(), 1);
		answer(ans);
	}
	
	int lo = K, hi = N+1;
	while (lo < hi) {
		int mid = lo + hi >> 1;
		ask(mid) + sum < A ? lo = mid + 1 : hi = mid;
	}
	if (lo <= N && ask(lo) + sum <= A+A) {
		vector<int> ans(K);
		iota(ans.begin(), ans.end(), 1);
		ans[K-1] = lo;
		answer(ans);
	}
	if (lo-- == K) {
		impossible();
	}
	
	vector<int> lft(K-1), rht = {lo};
	sum += ask(lo);
	iota(lft.begin(), lft.end(), 1);
	reverse(lft.begin(), lft.end());
	for (int i = lo-1; i > max(K-1, lo-K) && sum < A; i--) {
		sum += ask(i) - ask(lft.back());
		lft.pop_back();
		rht.push_back(i);
	}
	
	if (sum < A) {
		impossible();
	}
	for (int i : rht) {
		lft.push_back(i);
	}
	answer(lft);
}

Compilation message (stderr)

books.cpp: In function 'void solve(int, int, ll, int)':
books.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |   int mid = lo + hi >> 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