| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1269715 | seoul_korea | COVID tests (CEOI24_covid) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <string>
#include <numeric> // For std::iota (if needed for other strategies, not strictly for this one)
#include <cmath> // For math functions (if needed for P-dependent strategy)
// Global variables N and P are available from the template.
// extern int N;
// extern double P;
// The test_students function is provided by the judge environment.
// bool test_students(std::vector<bool> mask);
// Hàm đệ quy để tìm các mẫu dương tính trong một khoảng cụ thể [start_idx, end_idx].
// Nó sẽ cập nhật result_mask với các chỉ số của các mẫu dương tính.
void find_positive_in_range(int start_idx, int end_idx, std::vector<bool>& result_mask) {
if (start_idx > end_idx) {
return; // Khoảng không hợp lệ hoặc rỗng
}
// Tạo một mặt nạ cho khoảng hiện tại [start_idx, end_idx].
// Tất cả các phần tử khác ngoài khoảng này sẽ là false.
std::vector<bool> current_test_mask(N, false);
for (int i = start_idx; i <= end_idx; ++i) {
current_test_mask[i] = true;
}
// Thực hiện truy vấn xét nghiệm cho nhóm mẫu này.
bool is_positive_in_current_range = test_students(current_test_mask); [7]
if (!is_positive_in_current_range) {
// Không có mẫu dương tính nào trong khoảng này.
// Toàn bộ nhánh tìm kiếm này có thể được cắt bỏ.
return;
}
// Nếu có mẫu dương tính trong khoảng này:
if (start_idx == end_idx) {
// Đây là một khoảng chỉ có một phần tử, và nó đã được xác định là dương tính.
// Vì vậy, mẫu của học sinh này chắc chắn dương tính.
result_mask[start_idx] = true;
return;
}
// Đối với các khoảng có nhiều hơn một phần tử, chia nó thành hai nửa và đệ quy.
int mid_idx = start_idx + (end_idx - start_idx) / 2;
// Đệ quy kiểm tra nửa trái.
find_positive_in_range(start_idx, mid_idx, result_mask);
// Đệ quy kiểm tra nửa phải.
find_positive_in_range(mid_idx + 1, end_idx, result_mask);
}
// Hàm này sẽ được gọi một lần cho mỗi kịch bản.
std::vector<bool> find_positive() {
std::vector<bool> result_mask(N, false); // Khởi tạo tất cả học sinh là âm tính.
// Bắt đầu chiến lược phân tách nhị phân từ toàn bộ dải mẫu [0, N-1].
find_positive_in_range(0, N - 1, result_mask);
return result_mask;
}