제출 #523881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523881		fatemetmhr	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	2752 KiB

books

// Be name khoda //
#include <bits/stdc++.h>
#include "books.h"
 
using namespace std;
 
typedef long long ll;
 
const int maxn5 = 3e5 + 10;
const int lg    = 20;
 
#define pb    push_back
#define se    second
#define fi    first
 
//
// --- 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 <int> ret;
ll a[maxn5];

inline ll req(int i){
	if(a[i] != -1)
		return a[i];
	a[i] = skim(i);
	return a[i];
}

void solve(int N, int K, long long A, int S) {
	int n = N;
	int k = K;
	memset(a, -1, sizeof a);
	//cout << 1 / 0 << endl;
	
	int lo = 0, hi = n + 1;
	while(hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if(req(mid) <= A)
			lo = mid;
		else
			hi = mid;
	}
	
	
	if(lo == 0)
		impossible();
	if(lo < n){
		ll have = 0;
		for(int i = 1; i < k; i++)
			have += req(i);
		if(have + req(hi) <= 2 * A){
			for(int i = 1; i < k; i++)
				ret.pb(i);
			ret.pb(hi);
			answer(ret);
		}
	}
	
	for(int i = 0; i <= k; i++){
		ll have = 0;
		for(int r = 1; r <= i; r++)
			have += req(r);
		for(int r = lo - (k - i) + 1; r <= lo; r++)
			have += req(r);
		if(have >= A && have <= 2 * A){
			for(int r = 1; r <= i; r++)
				ret.pb(r);
			for(int r = lo - (k - i) + 1; r <= lo; r++)
				ret.pb(r);
			answer(ret);
		}
	}
	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