Submission #1311817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311817		Boycl07	Hack (APIO25_hack)	C++20	0 / 100	1 ms	332 KiB

hack

#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

// Khai báo hàm interactor
long long collisions(std::vector<long long> x);

namespace {
    // Hàm kiểm tra xem N có nằm trong khoảng [1, limit] không.
    // Sử dụng tính chất Difference Set: Tạo tập hợp S sao cho các hiệu số |x - y| 
    // bao phủ toàn bộ các số từ 1 đến limit.
    // Nếu collisions(S) > 0 => tồn tại x, y sao cho |x - y| chia hết cho n.
    // Vì max(|x-y|) ~ limit, điều này ngụ ý n <= limit.
    // Chi phí: ~ 2 * sqrt(limit)
    bool check(long long limit) {
        if (limit < 1) return false;
        
        // Chọn B ~ sqrt(limit)
        long long B = std::sqrt(limit);
        if (B * B < limit) B++;

        std::vector<long long> s;
        s.reserve(2 * B + 5);

        // Phần 1: 1, 2, ..., B
        for (long long i = 1; i <= B; ++i) s.push_back(i);
        
        // Phần 2: B, 2B, 3B, ..., B*B
        // Đảm bảo bao phủ đến limit
        long long current = B;
        while (current <= limit) { // Chỉ cần bao phủ đến limit là đủ
            s.push_back(current);
            current += B;
        }
        // Thêm một phần tử cuối để chắc chắn bao phủ phần dư nếu có
        if (s.back() < limit) s.push_back(limit); 

        // Sort và Unique để tối ưu
        std::sort(s.begin(), s.end());
        s.erase(std::unique(s.begin(), s.end()), s.end());

        return collisions(s) > 0;
    }

    // Hàm thực hiện Binary Search trên đáp án trong đoạn [L, R]
    int binary_search_n(long long L, long long R) {
        long long ans = R;
        while (L <= R) {
            long long mid = L + (R - L) / 2;
            
            // Kiểm tra xem n có nằm trong [1, mid] không
            if (check(mid)) {
                ans = mid;
                R = mid - 1; // Tìm kiếm kết quả nhỏ hơn
            } else {
                L = mid + 1; // n lớn hơn mid
            }
        }
        return (int)ans;
    }
}

int hack() {
    // CHIẾN THUẬT: PHÂN TẦNG ĐỂ TỐI ƯU ĐIỂM SỐ
    
    // Giai đoạn 1: Kiểm tra Subtask 1 & 2 (N <= 1,000,000)
    // Chi phí check(10^6) chỉ khoảng 2000 query. Rất rẻ.
    // Nếu N nằm trong vùng này, ta Binary Search tốn rất ít chi phí -> Ăn trọn điểm 2 subtask đầu.
    if (check(1000000)) {
        return binary_search_n(1, 1000000);
    }

    // Giai đoạn 2: N > 1,000,000 (Subtask 3)
    // Ta Binary Search trên vùng còn lại [10^6 + 1, 10^9].
    // Chi phí sẽ là tổng chuỗi log * sqrt(mid).
    return binary_search_n(1000001, 1000000000);
}

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