Submission #1311808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311808		Boycl07	Hack (APIO25_hack)	C++20	0 / 100	177 ms	4292 KiB

hack

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

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

namespace {
    std::vector<long long> get_divisors(long long val, long long limit) {
        std::vector<long long> divs;
        for (long long i = 1; i * i <= val; ++i) {
            if (val % i == 0) {
                if (i > limit) divs.push_back(i);
                if (val / i > limit && val / i != i) divs.push_back(val / i);
            }
        }
        return divs;
    }

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

int hack() {
    // --- Phase 1: Difference Set Construction ---
    // We construct a set that covers all differences up to ~490,000 using only ~1400 elements.
    // Set S = {1, 2, ..., B} U {B, 2B, 3B, ..., B*B}
    const long long B = 700;
    std::vector<long long> diff_set;
    for (int i = 1; i <= B; ++i) diff_set.push_back(i);
    for (int i = 1; i <= B; ++i) diff_set.push_back(i * B);
    
    // Sort and remove duplicates to be safe
    std::sort(diff_set.begin(), diff_set.end());
    diff_set.erase(std::unique(diff_set.begin(), diff_set.end()), diff_set.end());

    if (collisions(diff_set) > 0) {
        // We know n is likely small (<= 490,000).
        // Use binary search on the standard range {1...k} to find exact n.
        // We can search up to B*B safely.
        int low = 2, high = B * B + 100; 
        int ans = high;
        
        // Standard Binary Search
        while (low <= high) {
            int mid = low + (high - low) / 2;
            // Create query {1, 2, ..., mid}
            std::vector<long long> q(mid);
            std::iota(q.begin(), q.end(), 1);
            
            if (collisions(q) > 0) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans - 1;
    }

    // --- Phase 2: Birthday Attack ---
    // Since we cleared small n, we can use a moderate K.
    // K = 28000. 
    // Initial query: 28k. Isolation: ~28k. Total ~56k.
    // Total including Phase 1 < 60k. 
    // This allows multiple retries within the 110k budget or ensures high score.
    int K = 28000;
    
    std::mt19937_64 rng(1337); 
    std::uniform_int_distribution<long long> dist(1, 20000000000LL);

    while (true) {
        std::vector<long long> current_set;
        current_set.reserve(K);
        std::set<long long> distinct_check;
        
        while (current_set.size() < K) {
            long long val = dist(rng);
            if (distinct_check.insert(val).second) {
                current_set.push_back(val);
            }
        }

        if (collisions(current_set) > 0) {
            // Isolate
            while (true) {
                // Optimization: Brute force differences for small sets
                if (current_set.size() <= 64) { 
                    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]);
                            // Only check divisors > B (since we ruled out smaller n in Phase 1)
                            // Actually, let's just check > 1 to be safe, cost is negligible here.
                            std::vector<long long> cands = get_divisors(diff, 1);
                            for (long long cand : cands) {
                                if (check_n(cand)) return (int)cand;
                            }
                        }
                    }
                    break; // Should not reach here if collision exists
                }

                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());

                if (collisions(left_part) > 0) {
                    current_set = left_part;
                } else if (collisions(right_part) > 0) {
                    current_set = right_part;
                } else {
                    std::shuffle(current_set.begin(), current_set.end(), rng);
                }
            }
        }
    }
    
    return -1;
}

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