Submission #858385

#	Time	Username	Problem	Language	Result	Execution time	Memory
858385		lovrot	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	684 KiB

books

#include "books.h"
#include <cstdio> 
#include <algorithm> 
#include <cstring> 
#include <vector> 

#define EB emplace_back

using namespace std;

typedef long long ll; 

const int N = 1e5 + 10;

//
// --- 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.
//

// --- Sample input ---
// N K A S

int n;
ll a, BIO[N];

ll _skim(int x) {
	if(x <= 0 || x > n) return 0;
	if(BIO[x]) return BIO[x];
	return BIO[x] = skim(x); 
}

void _answer(ll sum, int l, int r, int _l, int _r) {
	if(sum < a || sum > 2 * a) return;
	vector<int> ANS;
	for(int i = l; i < r; ++i) ANS.EB(i); 
	for(int i = _l; i < _r; ++i) ANS.EB(i); 
	answer(ANS);
}
	
void solve(int _n, int k, ll _a, int s) {
	n = _n;
	a = _a;

	int lo = 0, hi = n + 1;
	while(hi - lo > 1) {
		int mi = (lo + hi) / 2;
		if(_skim(mi) < a) lo = mi;
		else hi = mi;
	}

	if(n < k || hi < k) impossible();
	
	for(int i = 1; i <= k; ++i) _skim(i);
	for(int i = 0; i < k; ++i) _skim(lo - i); 	

	ll sum = 0;
	for(int i = lo - k + 1; i <= lo; ++i) sum += _skim(i);
	
	if(lo >= k) {
		_answer(sum, 0, 0, lo - k + 1, lo + 1);
//		printf("%lld\n", sum);
		for(int i = lo - k + 1, j = 1; i <= lo; ++i, ++j) {
			sum += _skim(j) - _skim(i);
			_answer(sum, 1, j + 1, i + 1, lo + 1);
		}
	}
	
	if(hi <= n) {
		sum = _skim(hi);
		for(int i = 1; i < k; ++i) sum += _skim(i);
		_answer(sum, 1, k, hi, hi + 1);
	}

	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