Submission #1179703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179703		WH8	A Difficult(y) Choice (BOI21_books)	C++20	20 / 100	1 ms	1176 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;
    int ans=N+1;
    vector<long long> val(N+1, -1);
    //~ for(int i=1;i<=N;i++){
		//~ val[i]=skim(i);
	//~ }
	//~ ans=lower_bound(val.begin(),val.end(),A)-val.begin();
	//~ for(int i=1;i<=N;i++){
		//~ for(int j=i+1;j<=N;j++){
			//~ for(int k=j+1;k<=N;k++){
				//~ long long cur = val[i]+val[j]+val[k];
				//~ if(cur<=2*A and cur>=A){
					//~ answer({i,j,k});
					//~ return;
				//~ }
			//~ }
		//~ }
	//~ }
	//~ impossible();
    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;
		long long sm=0;
		for(int i=1;i<=k-1;i++){
			sm+=(val[i]==-1? skim(i) : val[i]);
			out.push_back(i);
		}
		out.push_back(ans);
		sm+=(val[ans]==-1? skim(ans) : val[ans]);
		if(sm>=A and sm <= 2*A){
			answer(out);
			return;
		}
		else if (ans==k){
			impossible();
			return;
		}
	}
	vector<pair<long long,int>> pref, suff;
	for(int i=1;i<=k;i++){
		pref.push_back({(val[i]==-1? skim(i) : val[i]),i});
	}
	for(int i=ans-1;i>=ans-k;i--){
		suff.push_back({(val[i]==-1? skim(i) : val[i]),i});
	}
	for(int i=0;i<=k;i++){
		long long 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: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20