Submission #917004

#	Time	Username	Problem	Language	Result	Execution time	Memory
917004		NK_	A Difficult(y) Choice (BOI21_books)	C++17	20 / 100	35 ms	600 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, ll>;
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) {
		++Q; if (Q > S) exit(0-0);
		return skim(x + 1);
	};

	int lo = 0, hi = N - 1;
	for(int r = 0; r < 18; r++) {
		if (lo >= hi) break;
		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) X.pb(mp(ask(i), i));

	// for(auto& p : X) cout << "(" << p.f << ", " << p.s << ") ";
	// cout << endl;
	
	int M = int(size(X)); assert(M <= 2 * K && S >= 0);
	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) {
			res.pb(X[i].s + 1);
			sum += X[i].f;
		}

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

		if (A <= sum && sum <= 2LL * A) {
			answer(res); return;
		}
	}
	
	impossible();
}

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