Submission #1179541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179541		WH8	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	1 ms	804 KiB

books

#include <bits/stdc++.h>

#include "books.h"
#define f first
#define s second
using namespace std;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

void solve(int N, int k, long long A, int S) {
    int hi=N,lo=1,m,ans=N+1;
    vector<int> val(N+1, 0);
    for(int i=1;i<=N;i++){
		val[i]=skim(i);
	}
	ans=lower_bound(val.begin(),val.end(),A)-val.begin();
	
    //~ while(lo<=hi){
		//~ m=(lo+hi)/2;
		//~ val[m]=skim(m);
		//~ if(val[m]>=A){
			//~ ans=m;
			//~ hi=m-1;
		//~ }
		//~ else{
			//~ lo=m+1;
		//~ }
	//~ }
	if(ans<k){
		impossible();
		return;
	}
	if(true){
		vector<int> out;
		int sm=0;
		for(int i=1;i<=k-1;i++){
			sm+=val[i];
			out.push_back(i);
		}
		out.push_back(ans);
		sm+=val[ans];
		if(sm>=A and sm <= 2*A){
			answer(out);
			return;
		}
		else if (ans==k){
			impossible();
			return;
		}
	}
	vector<pair<int,int>> pref, suff;
	for(int i=1;i<=k;i++){
		pref.push_back({val[i],i});
	}
	for(int i=ans-1;i>=ans-k;i--){
		suff.push_back({val[i],i});
	}
	for(int i=0;i<=k;i++){
		int check2=0;
		vector<int> out;
		for(int j=0;j<i;j++){
			check2+=pref[j].f;
			out.push_back(pref[j].s);
		}
		for(int j=0;j<k-i;j++){
			check2+=suff[j].f;
			out.push_back(suff[j].s);
		}
		if(check2>=A and check2 <= 2 *A){
			answer(out);
			return;
		}
	}
   impossible();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20