| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1311813 | Boycl07 | Hack (APIO25_hack) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
// Hàm grader cung cấp
long long collisions(std::vector<long long> x);
namespace {
// Hàm kiểm tra xem n có phải là ứng viên đúng không (Cost: 2)
bool check_n(long long n) {
if (n <= 0) return false;
return collisions({1, n + 1}) > 0;
}
// Hàm lấy ước số (để check kết quả cuối cùng)
std::vector<long long> get_divisors(long long val) {
std::vector<long long> divs;
for (long long i = 1; i * i <= val; ++i) {
if (val % i == 0) {
divs.push_back(i);
if (val / i != i) divs.push_back(val / i);
}
}
std::sort(divs.begin(), divs.end());
return divs;
}
// CHẶT NHỊ PHÂN TRÊN MẢNG (Divide & Conquer)
// Thay vì random, ta chia đôi mảng để tìm vùng có xung đột
int find_collision_in_set(std::vector<long long>& vec) {
// Base case: Nếu mảng nhỏ, vét cạn mọi cặp
if (vec.size() <= 20) {
for (int i = 0; i < vec.size(); ++i) {
for (int j = i + 1; j < vec.size(); ++j) {
long long diff = std::abs(vec[i] - vec[j]);
if (diff == 0) continue;
// Thử các ước của hiệu số
for (long long d : get_divisors(diff)) {
if (d > 1 && check_n(d)) return (int)d;
}
}
}
return -1;
}
// Chia đôi mảng: Lấy nửa trái (Left) và nửa phải (Right)
int mid = vec.size() / 2;
std::vector<long long> left_part(vec.begin(), vec.begin() + mid);
std::vector<long long> right_part(vec.begin() + mid, vec.end());
// Kiểm tra nửa trái
if (collisions(left_part) > 0) {
return find_collision_in_set(left_part);
}
// Kiểm tra nửa phải
if (collisions(right_part) > 0) {
return find_collision_in_set(right_part);
}
// Nếu cả 2 nửa đều không có, tức là xung đột nằm chéo (1 số bên trái, 1 số bên phải).
// Để đơn giản (không random), ta gộp lại theo cách so le hoặc trộn lại.
// Cách đơn giản nhất để xử lý case này mà không random:
// Giữ nguyên phần tử nhưng đảo vị trí để lần chia sau nó nằm cùng phía.
std::vector<long long> mixed;
for(size_t i=0; i<left_part.size(); ++i) {
if (i % 2 == 0) mixed.push_back(left_part[i]);
else mixed.push_back(right_part[i % right_part.size()]); // Trộn
}
for(size_t i=0; i<right_part.size(); ++i) {
if (i % 2 == 0) mixed.push_back(right_part[i]);
else mixed.push_back(left_part[i % left_part.size()]); // Trộn
}
// Đảm bảo kích thước không đổi và thử lại
if (mixed.size() != vec.size()) mixed = vec; // Fallback
// Cắt bỏ bớt phần tử để hội tụ nếu trộn không hiệu quả (heuristic)
mixed.pop_back();
return find_collision_in_set(mixed);
}
}
int hack() {
// 1. CHẶT NHỊ PHÂN CHO N NHỎ (<= 2500)
// Kiểm tra nhanh dải [1...2500]
std::vector<long long> small_q(2500);
std::iota(small_q.begin(), small_q.end(), 1);
if (collisions(small_q) > 0) {
int l = 2, r = 2500, ans = 2500;
while (l <= r) {
int mid = l + (r - l) / 2;
std::vector<long long> q(mid);
std::iota(q.begin(), q.end(), 1);
if (collisions(q) > 0) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans - 1;
}
// 2. GIẢI QUYẾT N LỚN (<= 10^9) BẰNG MẢNG CHÊNH LỆCH
// Tạo mảng bao phủ hiệu số đến 10^9: {1..K} U {K, 2K..K*K}
// K = 32000 => K*K > 10^9. Size mảng ~ 64000.
const long long K = 32000;
std::vector<long long> big_set;
for (long long i = 1; i <= K; ++i) big_set.push_back(i);
for (long long i = 1; i <= K; ++i) big_set.push_back(i * K);
// Xóa trùng và sort
std::sort(big_set.begin(), big_set.end());
big_set.erase(std::unique(big_set.begin(), big_set.end()), big_set.end());
// Chắc chắn có xung đột trong big_set, dùng hàm chặt nhị phân mảng để tìm
return find_collision_in_set(big_set);