Submission #938218

#	Time	Username	Problem	Language	Result	Execution time	Memory
938218		Gromp15	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	5 ms	600 KiB

books

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()

#include "books.h"

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
//
// --- 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.
//
//skim(x)
//impossible()
//answer(vector<int>)
const int NX = 1000;
vector<ll> mem(NX+1, -1);
ll ask(int x) {
	if (~mem[x]) return mem[x];
	return mem[x] = skim(x);
}
void solve(int N, int K, long long A, int S) {
	assert(N <= NX);
	// find first K and last K
	vector<bool> used(N+1);
	vector<ar<ll, 2>> vals;
	for (int i = 1; i <= K; i++) {
		vals.push_back({i, ask(i)});
		used[i] = 1;
		S--;
	}
	for (int i = N; i > max(K, N - K); i--) {
		vals.push_back({i, ask(i)});
		used[i] = 1;
		S--;
	}
	vector<vector<pair<ll, vector<int>>>> good(K);
	for (int mask = 0; mask < 1 << vals.size(); mask++) {
		int cnt = __builtin_popcount(mask);
		if (cnt <= K) {
			ll sum = 0;
			vector<int> cur;
			for (int i = 0; i < (int)vals.size(); i++) if (mask >> i & 1) {
				sum += vals[i][1];
				cur.emplace_back(vals[i][0]);
			}
			if (cnt == K && sum >= A && sum <= 2*A) {
				answer(cur);
				return;
			}
			if (cnt < K && sum < A) {
				good[cnt].push_back({sum, cur});
			}
		}
	}
	vector<int> remaining;
	for (int i = 1; i <= N; i++) if (!used[i]) remaining.emplace_back(i);
	shuffle(all(remaining), rng);
	vector<ar<ll, 2>> guesses;
	for (int t = 0; t < min(S, (int)remaining.size()); t++) { // search for things in between
		int pos = remaining[t];
		guesses.push_back({ask(pos), pos});
	}
	sort(all(guesses));
	vector<int> time(N+1);
	int timer = 1;
	vector<pair<ll, vector<int>>> mins(K+1, pair<ll, vector<int>>{(ll)1e18, {}});
	for (int i = 0; i <= min(int(guesses.size()) - 1, K); i++) {
		ll sum = 0;
		vector<int> who(i);
		for (int j = 0; j < i; j++) { 
			sum += guesses[j][0];
			who[j] = guesses[j][1];
		}
		mins[i] = {sum, who};
	}
	for (int i = 0; i < K; i++) { // choose this many from the side
		for (const auto &[val, who] : good[i]) {
			timer++;
			int left = K - i;
			ll cur_sum = val;
			assert(cur_sum < A);
			vector<int> tmp;
			tmp.reserve(K);
			for (int t = 0; t < left; t++) {
				ll min_sum = cur_sum + mins[left-t].first;
				if (min_sum > 2*A) break;
				if (min_sum >= A) {
					auto ans = who;
					for (int x : tmp) ans.emplace_back(x);
					for (int x : mins[left-t].second) ans.emplace_back(x);
					answer(ans);
					return;
				}
				// we want to choose s.t. cur_sum <= 2A
				ll req = 2*A - cur_sum;
				// [0, req]
				auto it = upper_bound(guesses.begin(), guesses.end(), ar<ll, 2>{req, INT_MAX});
				if (it == guesses.begin()) {
					break;
				}
				it--;
				auto [there, idx] = *it;
				while (there >= 0 && time[there] == timer) there--;
				if (there >= 0) {
					cur_sum += guesses[idx][0];
					assert(cur_sum <= 2 * A);
					tmp.emplace_back(guesses[idx][1]);
					if (cur_sum + mins[left-t-1].first >= A) {
						auto ans = who;
						for (int x : tmp) ans.emplace_back(x);
						for (int x : mins[left-t-1].second) ans.emplace_back(x);
						answer(ans);
						return;
					}
				}
				else break;
			}
		}
	}
	impossible();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20