Submission #1179717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179717		WH8	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	1192 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.
//

vector<long long> val(100005, -1);
long long qry(int x){
	if(val[x]!=-1)return val[x];
	return val[x]=skim(x);
}

void solve(int N, int k, long long A, int S) {
    int hi=N,lo=1,m;
    int ans=N+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;
		long long c=qry(m);
		if(c>=A){
			ans=m;
			hi=m-1;
		}
		else{
			lo=m+1;
		}
	}
	if(ans<k){
		impossible();
		return;
	}

	if(ans!=N+1){ // if >= A exists
		vector<int> out;
		long long sm=0;
		for(int i=1;i<=k-1;i++){ //k-1 prefix
			sm+=qry(i);
			out.push_back(i);
		}
		out.push_back(ans); // first occurence >= A
		sm+=qry(ans);
		if(sm>=A and sm <= 2*A){
			answer(out);
			return;
		}
		else if (ans==k){ // then there wouldnt be another config that worsk
			impossible();
			return;
		}
	}
	
	for(int i=0;i<=k;i++){ // prefix size
		long long check2=0;
		vector<int> out;
		for(int j=1;j<=i;j++){
			check2+=qry(j); // prefix
			out.push_back(j);
		}
		for(int j=ans-1;j>=ans-(k-i);j--){
			check2+=qry(j); // suffix
			out.push_back(j);
		}
		if(check2>=A and check2 <= 2*A){
			answer(out);
			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