oj.uz

Submission #938219

# Submission time Handle Problem Language Result Execution time Memory
938219 2024-03-05T02:55:34 Z Gromp15 A Difficult(y) Choice (BOI21_books) C++17
10 / 100
 136 ms 42508 KB 
#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 = 1e6;
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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8024 KB Output is correct
3 Runtime error 12 ms 16512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8024 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Runtime error 13 ms 16476 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 102 ms 9240 KB Output is correct
4 Correct 101 ms 9176 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 5 ms 9424 KB Output is correct
7 Correct 5 ms 9164 KB Output is correct
8 Correct 136 ms 41988 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 102 ms 9240 KB Output is correct
4 Correct 101 ms 9176 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 5 ms 9424 KB Output is correct
7 Correct 5 ms 9164 KB Output is correct
8 Correct 136 ms 41988 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 3 ms 8292 KB Output is correct
12 Correct 105 ms 9256 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 6 ms 9168 KB Output is correct
15 Correct 5 ms 9168 KB Output is correct
16 Correct 5 ms 9168 KB Output is correct
17 Correct 127 ms 42508 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Runtime error 112 ms 18456 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 102 ms 9240 KB Output is correct
4 Correct 101 ms 9176 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 5 ms 9424 KB Output is correct
7 Correct 5 ms 9164 KB Output is correct
8 Correct 136 ms 41988 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 3 ms 8292 KB Output is correct
12 Correct 105 ms 9256 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 6 ms 9168 KB Output is correct
15 Correct 5 ms 9168 KB Output is correct
16 Correct 5 ms 9168 KB Output is correct
17 Correct 127 ms 42508 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Runtime error 112 ms 18456 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 102 ms 9240 KB Output is correct
4 Correct 101 ms 9176 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 5 ms 9424 KB Output is correct
7 Correct 5 ms 9164 KB Output is correct
8 Correct 136 ms 41988 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 3 ms 8292 KB Output is correct
12 Correct 105 ms 9256 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 6 ms 9168 KB Output is correct
15 Correct 5 ms 9168 KB Output is correct
16 Correct 5 ms 9168 KB Output is correct
17 Correct 127 ms 42508 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Runtime error 112 ms 18456 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 102 ms 9240 KB Output is correct
4 Correct 101 ms 9176 KB Output is correct
5 Correct 5 ms 9172 KB Output is correct
6 Correct 5 ms 9424 KB Output is correct
7 Correct 5 ms 9164 KB Output is correct
8 Correct 136 ms 41988 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 3 ms 8292 KB Output is correct
12 Correct 105 ms 9256 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 6 ms 9168 KB Output is correct
15 Correct 5 ms 9168 KB Output is correct
16 Correct 5 ms 9168 KB Output is correct
17 Correct 127 ms 42508 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Runtime error 112 ms 18456 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -