제출 #573626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573626		amunduzbaev	A Difficult(y) Choice (BOI21_books)	C++17	60 / 100	3 ms	1988 KiB

books

#include <bits/stdc++.h>

#include "books.h"
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;
using ll = long long;

void solve(int n, int k, ll a, int s) {
	vector<ll> is(n + 1, -1);
	int c = 0;
	auto ask = [&](int i){
		if(~is[i]) return is[i];
		assert(c < s);
		is[i] = skim(i), c++;
		return is[i];
	};
	
	int l = 1, r = n;
	while(l < r){
		int m = (l + r) >> 1;
		if(a < ask(m)) r = m;
		else l = m + 1;
	}
	
	int p = l;
	if(ask(p) > a * 2) p--;
	if(p < k){
		impossible();
		return;
	}
	
	vector<ll> L, R;
	for(int i=1;i<=k;i++){
		L.push_back(ask(i));
	}
	
	for(int i=p-k+1;i<=p;i++){
		R.push_back(ask(i));
	}
	
	if(accumulate(R.begin(), R.end(), 0ll) < a
	|| accumulate(L.begin(), L.end(), 0ll) > a * 2) { impossible(); return; }
	
	int fix=-1;
	for(int i=1;i<=k;i++){
		ll sum = 0;
		for(int j=0;j<i;j++) sum += L[j];
		for(int j=k-1;j>=i;j--) sum += R[j];
		if(sum > a * 2) continue;
		fix = i; break;
	}
	
	if(fix == -1) { impossible(); return; }
	ll sum = 0;
	for(int j=0;j<fix-1;j++) sum += L[j];
	for(int j=k-1;j>=fix;j--) sum += R[j];
	l = fix, r = p - k + fix;
	while(l < r){
		int m = (l + r) >> 1;
		if(ask(m) + sum < a) l = m + 1;
		else r = m;
	}
	
	if(ask(l) + sum <= a * 2 && a <= ask(l) + sum){
		vector<int> res;
		for(int i=1;i<fix;i++) res.push_back(i);
		res.push_back(l);
		for(int i=p-k+fix+1;i<=p;i++) res.push_back(i);
		answer(res);
		return;
	} else impossible();
}

/*

15 3 42 12
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

*/

• 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