제출 #573710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573710		amunduzbaev	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	22 ms	1072 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> pos, val;
	for(int i=1;i<=k;i++){
		pos.push_back(i);
		val.push_back(ask(i));
	}
	for(int i=max(k, p-k) + 1;i<=p;i++){
		pos.push_back(i);
		val.push_back(ask(i));
	}
	int m = pos.size(), res = -1;
	for(int mask=0;mask < (1 << m);mask++){
		if(__builtin_popcount(mask) != k) continue;
		ll sum = 0;
		for(int i=0;i<m;i++){
			if(mask >> i & 1) sum += val[i];
		}
		
		if(a <= sum && sum <= a * 2){
			res = mask;
		}
	}
	
	if(res == -1) { impossible(); return; }
	vector<int> rr;
	for(int i=0;i<m;i++){
		if(res >> i & 1) rr.push_back(pos[i]);
	}
	//~ for(auto x : rr) cout<<is[x]<<" ";
	//~ cout<<"\n";
	answer(rr);
	
	//~ 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;
	//~ }
	
	//~ 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;
	//~ }
	//~ sum += ask(l);
	//~ if(a <= sum && sum <= a * 2){
		//~ 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);
	//~ } 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: 20 / 20
• Subtask 7: 20 / 20