Submission #1179585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179585		emptypringlescan	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	408 KiB

books

#include <bits/stdc++.h>

#include "books.h"

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) {
    // TODO implement this function
    vector<pair<int,long long> > smol,beeg;
    long long ts=0,tb=0;
    for(int i=1; i<=K; i++){
		smol.push_back({i,skim(i)});
		ts+=smol.back().second;
	}
	vector<int> ans;
	if(ts>2ll*A){
		impossible();
		return;
	}
	else if(ts>=A){
		for(int i=1; i<=K; i++) ans.push_back(i);
		answer(ans);
		return;
	}
	int lo=1,hi=N+1,mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		long long x=skim(mid);
		if(x<A) lo=mid+1;
		else hi=mid;
	}
	long long more=2e17;
	if(lo!=N+1) more=skim(lo);
	if(more+ts-smol.back().second<=2ll*A){
		for(int i=1; i<K; i++) ans.push_back(i);
		ans.push_back(lo);
		answer(ans);
		return;
	}
	for(int i=K; i>0; i--){
		beeg.push_back({lo-i,skim(lo-i)});
		tb+=beeg.back().second;
	}
	if(tb<A){
		impossible();
		return;
	}
	else if(tb<=2ll*A){
		for(int i=1; i<=K; i++) ans.push_back(lo-i);
		answer(ans);
		return;
	}
	for(int i=0; i<K; i++){
		tb-=beeg[i].second;
		tb+=smol[i].second;
		if(A<=tb&&tb<=2ll*A){
			for(int j=0; j<=i; j++) ans.push_back(smol[j].first);
			for(int j=i+1; j<K; j++) ans.push_back(beeg[j].first);
			answer(ans);
			return;
		}
	}
	assert(false);
}

• 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