Submission #488894

#	Time	Username	Problem	Language	Result	Execution time	Memory
488894		CSQ31	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	328 KiB

books

#include <bits/stdc++.h>
 
#include "books.h"
using namespace std;
#define pb push_back
typedef long long int ll;
//bin search for 17
//then take prefix 10 and suffix 10
//in total 38 queries
ll a[111111];
ll ask(int x){
	if(a[x])return a[x];
	else return a[x] = skim(x);
}
void solve(int n, int k, ll A, int s) {
	int l = 1,r = n;
	while(r>=l){
		int mid = (l+r)/2;
		if(ask(mid)<A)l=mid+1;
		else r=mid-1;
	}
	ll sum = 0;
	for(int i=1;i<=k;i++)sum+=ask(i);
	
	
	vector<int>ans; //take k smallest elements
	if(sum>2*A)impossible();
	else if(sum>=A){
		for(int i=1;i<=k;i++)ans.pb(i);
		answer(ans);
		return;
	}
	
	//cout<<l<<'\n';
	if(l<=n && l>=k){ //take k-1 smallest elements and l if l exists
		sum = 0;
		for(int i=1;i<k;i++)sum+=ask(i);
		sum+=ask(l);
		
		if(sum>=A && sum<=2*A){
			for(int i=1;i<k;i++)ans.pb(i);
			ans.pb(l);
			answer(ans);
			return;
		}
	}
	l = min(l-1,n);
	if(l>=k){
		for(int i=0;i<=k;i++){ //try all prefix and suffix
			sum = 0;
			ans.clear();
			for(int j=1;j<=i;j++){
				sum+=ask(j);
				ans.pb(j);
			}
			int need = k-i;
			for(int j=0;j<need;j++){
				sum+=ask(l-j);
				ans.pb(l-j);
			}
			
			if(sum>=A && sum<=2*A){
				answer(ans);
				return;
			}
		}
	}
	impossible();
}

• 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