Submission #942974

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

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
typedef long long ll;
//
// --- 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.cpp grader.cpp
// in this folder.
//

void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    vector<ll> first;
    map<ll,ll> checked;
    ll total=0;
    for (int i=1;i<=K;i++){
		ll temp = skim(i);
		total += temp;
		first.push_back(temp);
		checked[i] = temp;
	}
	vector<int> ans;
	for (int i=1;i<=K;i++){
		ans.push_back(i);
	}
	if (total > A*2) impossible();
	if (total >= A) answer(ans);
	ll l=1,r=N+1;
	while (l<r){
		ll m = l+(r-l)/2;
		ll temp = skim(m);
		checked[m] = temp;
		if (temp<A) l=m+1;
		else r=m;
	}
	if (l<=K) impossible();
	if (l<=N){
		if (total-checked[K]+checked[l] <= 2*A) {
			vector<int> ans2;
			for (int i=1;i<K;i++){
				ans2.push_back(i);
			}
			ans2.push_back(l);
			answer(ans2);
		}
	}
	ll l2;
	if (checked[l-1]!=0) l2 = checked[l-1];
	else l2 = skim(l-1);
	checked[l-1] = l2;
	vector<int> ans2;
	ans2.push_back(l-1);
	if (l-1<=K) impossible();
	total -= checked[1];
	if (total + l2 >= A) {
		for (int i=2;i<=K;i++) ans2.push_back(i);
		answer(ans2);
	}
	total += l2;
	for (int i=0;i<K-1;i++){
		l--;
		if (checked[l-1]!=0) l2 = checked[l-1];
		else l2 = skim(l-1);
		checked[l-1] = l2;
		if (l-1<=K) impossible(); 
		ans2.push_back(l-1);
		total -= checked[i+2];
		if (total + l2 >= A){
			for (int j=i+3;j<=K;j++) ans2.push_back(j);
			answer(ans2);
		}
		total += l2;
	}
	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