oj.uz

Submission #938223

# Submission time Handle Problem Language Result Execution time Memory
938223 2024-03-05T03:07:10 Z Gromp15 A Difficult(y) Choice (BOI21_books) C++17
10 / 100
 127 ms 43152 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--;
				int there = it - guesses.begin();
				while (there >= 0 && time[there] == timer) there--;
				if (there >= 0) {
					time[there] = timer;
					cur_sum += guesses[there][0];
					assert(cur_sum <= 2 * A);
					tmp.emplace_back(guesses[there][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 8024 KB Output is correct
2 Correct 2 ms 8532 KB Output is correct
3 Correct 6 ms 8308 KB Output is correct
4 Correct 2 ms 8280 KB Output is correct
5 Correct 2 ms 8024 KB Output is correct
6 Correct 5 ms 8308 KB Output is correct
7 Incorrect 5 ms 8560 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #2
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 5 ms 8568 KB Output is correct
4 Correct 2 ms 8280 KB Output is correct
5 Correct 2 ms 8280 KB Output is correct
6 Correct 5 ms 8556 KB Output is correct
7 Incorrect 5 ms 8316 KB Incorrect
8 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 104 ms 9164 KB Output is correct
4 Correct 102 ms 9156 KB Output is correct
5 Correct 5 ms 9168 KB Output is correct
6 Correct 5 ms 9168 KB Output is correct
7 Correct 5 ms 9316 KB Output is correct
8 Correct 127 ms 42728 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 104 ms 9164 KB Output is correct
4 Correct 102 ms 9156 KB Output is correct
5 Correct 5 ms 9168 KB Output is correct
6 Correct 5 ms 9168 KB Output is correct
7 Correct 5 ms 9316 KB Output is correct
8 Correct 127 ms 42728 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 3 ms 8280 KB Output is correct
11 Correct 2 ms 8280 KB Output is correct
12 Correct 100 ms 9160 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 5 ms 9168 KB Output is correct
15 Correct 5 ms 9180 KB Output is correct
16 Correct 5 ms 9420 KB Output is correct
17 Correct 127 ms 43152 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 102 ms 9164 KB Output is correct
21 Correct 101 ms 9160 KB Output is correct
22 Correct 101 ms 9160 KB Output is correct
23 Incorrect 104 ms 9236 KB Incorrect
24 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 104 ms 9164 KB Output is correct
4 Correct 102 ms 9156 KB Output is correct
5 Correct 5 ms 9168 KB Output is correct
6 Correct 5 ms 9168 KB Output is correct
7 Correct 5 ms 9316 KB Output is correct
8 Correct 127 ms 42728 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 3 ms 8280 KB Output is correct
11 Correct 2 ms 8280 KB Output is correct
12 Correct 100 ms 9160 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 5 ms 9168 KB Output is correct
15 Correct 5 ms 9180 KB Output is correct
16 Correct 5 ms 9420 KB Output is correct
17 Correct 127 ms 43152 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 102 ms 9164 KB Output is correct
21 Correct 101 ms 9160 KB Output is correct
22 Correct 101 ms 9160 KB Output is correct
23 Incorrect 104 ms 9236 KB Incorrect
24 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 104 ms 9164 KB Output is correct
4 Correct 102 ms 9156 KB Output is correct
5 Correct 5 ms 9168 KB Output is correct
6 Correct 5 ms 9168 KB Output is correct
7 Correct 5 ms 9316 KB Output is correct
8 Correct 127 ms 42728 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 3 ms 8280 KB Output is correct
11 Correct 2 ms 8280 KB Output is correct
12 Correct 100 ms 9160 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 5 ms 9168 KB Output is correct
15 Correct 5 ms 9180 KB Output is correct
16 Correct 5 ms 9420 KB Output is correct
17 Correct 127 ms 43152 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 102 ms 9164 KB Output is correct
21 Correct 101 ms 9160 KB Output is correct
22 Correct 101 ms 9160 KB Output is correct
23 Incorrect 104 ms 9236 KB Incorrect
24 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 104 ms 9164 KB Output is correct
4 Correct 102 ms 9156 KB Output is correct
5 Correct 5 ms 9168 KB Output is correct
6 Correct 5 ms 9168 KB Output is correct
7 Correct 5 ms 9316 KB Output is correct
8 Correct 127 ms 42728 KB Output is correct
9 Correct 2 ms 8280 KB Output is correct
10 Correct 3 ms 8280 KB Output is correct
11 Correct 2 ms 8280 KB Output is correct
12 Correct 100 ms 9160 KB Output is correct
13 Correct 101 ms 9160 KB Output is correct
14 Correct 5 ms 9168 KB Output is correct
15 Correct 5 ms 9180 KB Output is correct
16 Correct 5 ms 9420 KB Output is correct
17 Correct 127 ms 43152 KB Output is correct
18 Correct 2 ms 8280 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 102 ms 9164 KB Output is correct
21 Correct 101 ms 9160 KB Output is correct
22 Correct 101 ms 9160 KB Output is correct
23 Incorrect 104 ms 9236 KB Incorrect
24 Halted 0 ms 0 KB -