Submission #1311810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311810		Boycl07	Hack (APIO25_hack)	C++20	28.70 / 100	292 ms	1676 KiB

hack

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

// Declare the interactor
long long collisions(std::vector<long long> x);

namespace {
    // Helper to find divisors of difference
    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;
    }

    // Verify candidate N (Cost: 2)
    bool check_n(long long n) {
        if (n <= 0) return false;
        std::vector<long long> q = {1, n + 1};
        return collisions(q) > 0;
    }

    // Standard Divide & Conquer to isolate a colliding pair
    // Guaranteed to terminate because the input set has collisions.
    int solve_collision(std::vector<long long>& current_set, long long min_n, std::mt19937_64& rng) {
        while (true) {
            // Optimization: If set is small, brute force differences
            if (current_set.size() <= 24) { 
                for (size_t i = 0; i < current_set.size(); ++i) {
                    for (size_t j = i + 1; j < current_set.size(); ++j) {
                        long long diff = std::abs(current_set[i] - current_set[j]);
                        if (diff < min_n) continue; // Skip if we know N is larger
                        
                        // Check divisors of the difference
                        std::vector<long long> cands = get_divisors(diff);
                        for (long long cand : cands) {
                            if (cand < min_n) continue;
                            if (check_n(cand)) return (int)cand;
                        }
                    }
                }
                break; // Should not happen if collision exists
            }

            // Split
            int sz = current_set.size();
            int mid = sz / 2;
            std::vector<long long> left_part(current_set.begin(), current_set.begin() + mid);
            std::vector<long long> right_part(current_set.begin() + mid, current_set.end());

            // Check Left
            if (collisions(left_part) > 0) {
                current_set = left_part;
            } 
            // Check Right
            else if (collisions(right_part) > 0) {
                current_set = right_part;
            } 
            // Crossing Collision
            else {
                // Must shuffle to create a new random split
                std::shuffle(current_set.begin(), current_set.end(), rng);
            }
        }
        return -1;
    }
}

int hack() {
    std::mt19937_64 rng(1337); 

    // --- Phase 1: Deterministic Check for Small N (<= 1,000,000) ---
    // Construction: {1..B} U {B, 2B... B*B} with B=1000
    // Covers all differences up to 1,000,000.
    // Cost: ~2000.
    {
        const long long B = 1000;
        std::vector<long long> small_set;
        small_set.reserve(2 * B + 5);
        for (long long i = 1; i <= B; ++i) small_set.push_back(i);
        for (long long i = 1; i <= B; ++i) small_set.push_back(i * B);
        
        // Ensure distinctness
        std::sort(small_set.begin(), small_set.end());
        small_set.erase(std::unique(small_set.begin(), small_set.end()), small_set.end());

        if (collisions(small_set) > 0) {
            // N is small. Isolate it.
            return solve_collision(small_set, 1, rng);
        }
    }

    // --- Phase 2: Deterministic Check for Large N (up to 10^9) ---
    // Construction: {1..K} U {K, 2K... K*K} with K=32000
    // Covers all differences up to ~1.024 * 10^9.
    // Set Size: ~64,000.
    {
        const long long K = 32000;
        std::vector<long long> large_set;
        large_set.reserve(2 * K + 5);
        
        // Part A: {1, ..., K}
        for (long long i = 1; i <= K; ++i) large_set.push_back(i);
        // Part B: {K, 2K, ..., K*K}
        // Note: We go up to K*K + some buffer if needed, but K*K > 10^9 is enough.
        // K*K = 1,024,000,000.
        for (long long i = 1; i <= K; ++i) large_set.push_back(i * K);

        std::sort(large_set.begin(), large_set.end());
        large_set.erase(std::unique(large_set.begin(), large_set.end()), large_set.end());

        // This query guarantees a collision if N <= 10^9
        if (collisions(large_set) > 0) {
            // We know N > 1,000,000 from Phase 1, so we can pass that as min_n
            // to speed up the brute-force check at the leaf nodes.
            return solve_collision(large_set, 1000000, rng);
        }
    }

    // Fallback (should never be reached for N <= 10^9)
    return -1;
}

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