Submission #715281

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

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;

map<int,ll> cache;

ll query(int pos){
	if (cache.count(pos)) return cache[pos];
	cache[pos] = skim(pos);
	return cache[pos];
}

void solve(int N, int K, long long A, int S) {
	ll sum = 0;
	deque<int> ans;
	for (int i=1; i<=K; ++i){
		sum += query(i);
		ans.emplace_back(i);
	}
	if (A <= sum and sum <= 2*A){
		answer({ans.begin(),ans.end()});
		return;
	}
	if (sum > 2*A){
		impossible();
		return;
	}
	int res = K+1;
	for (int i=(1<<16); i>0; i /= 2){
		if (i+res < N and query(i+res) < A) res += i;
	}
	for (int i=res+1; i>=res-9; --i){
		if (i > N) continue;
		ll val = query(i)+sum-query(ans.back());
		if (i <= K){
			impossible();
			return;
		}
		if (val <= 2*A){
			sum = val;
			ans.emplace_front(i);
			ans.pop_back();
		}
		if (A <= val and val <= 2*A){
			answer({ans.begin(),ans.end()});
			return;
		}
	}
	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