Submission #1310302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310302		Boycl07	Hack (APIO25_hack)	C++20	39.50 / 100	283 ms	1428 KiB

hack

#include "hack.h"
#include <vector>
#include <numeric>
#include <algorithm>
#include <random>
#include <cmath>

// Declare the interactor provided by the judge

namespace {
    // Helper to find all divisors of val that are strictly greater than limit.
    // Since we constrain input values to ~10^10, val is small enough to factorize quickly.
    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);
            }
        }
        std::sort(divs.begin(), divs.end());
        return divs;
    }

    // Check if a candidate n is the correct answer
    // If n is correct, 1 and n+1 will collide (both map to bucket 1)
    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: Check for small n efficiently
    // If n <= 2500, a set of size 2501 {1..2501} guarantees a collision.
    const int SMALL_LIMIT = 2500;
    std::vector<long long> small_q(SMALL_LIMIT + 1);
    std::iota(small_q.begin(), small_q.end(), 1);
    
    if (collisions(small_q) > 0) {
        // Binary search to find the smallest k such that {1..k} has a collision.
        // The first collision occurs when k = n + 1.
        int low = 2, high = SMALL_LIMIT + 1;
        int ans = high;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            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: Solve for large n using Birthday Paradox
    // Use a fixed seed for consistency, or random_device if allowed.
    std::mt19937_64 rng(1337); 
    
    // CRITICAL OPTIMIZATION:
    // We restrict the random range to [1, 2*10^10].
    // This is > 10^9 (so collisions occur naturally based on n)
    // but small enough that |u - v| can be factorized instantly without TLE.
    std::uniform_int_distribution<long long> dist(1, 20000000000LL);

    // K = 50,000 fits the budget (approx 100k-110k total cost) and gives high collision prob.
    int K = 50000;
    
    // We loop until success. Even if one attempt fails, the retry will likely succeed.
    while (true) {
        std::vector<long long> current_set;
        current_set.reserve(K);
        
        // Generate distinct random numbers
        while (current_set.size() < K) {
            current_set.push_back(dist(rng));
        }
        std::sort(current_set.begin(), current_set.end());
        current_set.erase(std::unique(current_set.begin(), current_set.end()), current_set.end());
        // Refill if duplicates were removed (extremely rare)
        while (current_set.size() < K) {
            current_set.push_back(dist(rng));
            std::sort(current_set.begin(), current_set.end());
            current_set.erase(std::unique(current_set.begin(), current_set.end()), current_set.end());
        }

        if (collisions(current_set) > 0) {
            // Collision found. Use Randomized Divide & Conquer to find the pair.
            while (current_set.size() > 2) {
                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 {
                    // Collision is between Left and Right. Shuffle and retry split.
                    std::shuffle(current_set.begin(), current_set.end(), rng);
                }
            }
            
            // Calculate difference D = |u - v|. We know n | D.
            long long diff = std::abs(current_set[0] - current_set[1]);
            
            // Check divisors of D to find n.
            std::vector<long long> cands = get_divisors(diff, SMALL_LIMIT);
            for (long long cand : cands) {
                if (check_n(cand)) {
                    return (int)cand;
                }
            }
        }
        // If no collision in this random set, loop continues and tries a new set.
        // This prevents WA by ensuring we eventually find n.
    }
    
    return -1; // Should not be reached
}

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