Submission #942965

#	Time	Username	Problem	Language	Result	Execution time	Memory
942965		yhkhoo	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	1368 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.
//

#define ll long long

void solve(int N, int K, ll A, int S) {
	vector<int> ans;
	vector<ll> x(N+1, -1);
	ll lb = 0;
	for(int i=1; i<K; i++){
		x[i] = skim(i);
		lb += x[i];
	}
	if(lb + x[K-1] > 2*A){
		impossible();
		return;
	}
	int s=K, e=N, m;
	while(s<e){
		m = (s+e)/2;
		x[m] = skim(m);
		if(x[m] + lb < A){
			s = m+1;
		}
		else if(x[m] + lb > 2*A){
			e = m-1;
		}
		else{
			s = m;
			e = m;
		}
	}
	if(x[s] == -1) x[s] = skim(s);
	ll suu = x[s] + lb;
	if(suu > 2*A){
		if(s == K){
			impossible();
			return;
		}
		else{
			s--;
			suu = x[s] + lb;
		}
	}
	if(suu < A){
		for(int i=1; i<K; i++){
			suu -= x[i];
			if(x[s-i] == -1) x[s-i] = skim(s-i);
			suu += x[s-i];
			if(suu >= A){
				for(int j=i+1; j<K; j++){
					ans.push_back(j);
				}
				for(int j=s-i; j<=s; j++){
					ans.push_back(j);
				}
				answer(ans);
				return;
			}
		}
		impossible();
		return;
	}
	for(int i=1; i<K; i++){
		ans.push_back(i);
	}
	ans.push_back(s);
	answer(ans);
	return;
}

• 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