Submission #917009

#	Time	Username	Problem	Language	Result	Execution time	Memory
917009		NK_	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	41 ms	852 KiB

books

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
#include "books.h"

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair
#define pb push_back

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using pl = pair<ll, int>;
using vpl = V<pl>;


// g++-13 A.cpp grader.cpp

void solve(int N, int K, ll A, int S) {
	int Q = 0;
	auto ask = [&](int x) -> ll {
		++Q; if (Q > S) exit(0-0);
		return skim(x + 1);
	};

	int lo = 0, hi = N - 1;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		if (ask(mid) >= A) hi = mid;
		else lo = mid + 1;
	}

	lo = min(N - 1, lo);

	set<int> look;
	for(int i = 0; i < K; i++) { look.insert(i); look.insert(lo - i); }

	vpl X; for(auto& i : look) {
		if (i < 0 || i >= N) continue;
		X.pb(mp(ask(i), i));
	}

	int M = int(size(X)); 
	// cout << M << endl;
	assert(M <= 2 * K && Q < S);
	for(int msk = 0; msk < (1 << M); msk++) {
		if (__builtin_popcount(msk) != K) continue;

		ll sum = 0; vi res; for(int i = 0; i < M; i++) if ((msk >> i) & 1) {
			sum += X[i].f; res.pb(X[i].s + 1);
		}

		assert(int(size(res)) == K);

		if (1LL * A <= sum && sum <= 2LL * A) {
			answer(res);
		}
	}
	
	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