Submission #1256195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256195		MasterDebater	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	580 ms	424 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
const int N=2e5+10;
bool bio[N];
int binary_search(int lo,int hi,ll a){
	int res=0;
	while(lo<=hi){
		int mid=(lo+hi)/2;
		if(skim(mid)<a)res=mid,lo=mid+1;
		else hi=mid-1;
	}
	return res;
}
void solve(int N,int K,ll A,int S){
	int L=binary_search(1,N,A);
	vector<pii>v;
	for(int i=1;i<=K;i++)if(!bio[i])bio[i]=1,v.push_back({i,skim(i)});
	for(int i=max(1,L-K+1);i<=min(N,L+2);i++)if(!bio[i])bio[i]=1,v.push_back({i,skim(i)});
	int sz=v.size();
	for(int i=0;i<(1<<sz);i++){
		vector<int>ans;
		ans.clear();
		ll sum=0;
		for(int j=0;j<sz;j++)if((i>>j)&1)ans.push_back(v[j].F),sum+=v[j].S;
		if(ans.size()==K and sum>=A and sum<=2*A){
			answer(ans);
		}
	}
	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