Submission #1311814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311814		Boycl07	Hack (APIO25_hack)	C++20	0 / 100	13 ms	2820 KiB

hack

#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);
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 75