Submission #1310301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310301		Boycl07	Hack (APIO25_hack)	C++20	0 / 100	112 ms	1748 KiB

hack

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

// Declare the interactor function provided by the grading system
long long collisions(std::vector<long long> x);

namespace {
    // Helper to find all divisors of val that are strictly greater than limit
    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;
    }
}

int hack() {
    // Constants tuned for the 110,000 cost limit and 10^9 range
    const long long SMALL_LIMIT = 2000;
    const long long STRIDE = 21379; // A large prime number
    const int K = 48000; // K * STRIDE > 10^9, fits within budget
    
    // --- Phase 1: Eliminate small n ---
    // Query {1, 2, ..., 2000}
    std::vector<long long> small_query(SMALL_LIMIT);
    std::iota(small_query.begin(), small_query.end(), 1);
    
    if (collisions(small_query) > 0) {
        // If collisions exist, n < 2000. Binary search for the smallest size 
        // that causes a collision.
        int low = 2, high = SMALL_LIMIT;
        int ans = 2;
        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;
            }
        }
        // If {1..ans} has a collision but {1..ans-1} doesn't, 
        // then 'ans' collided with '1' (or similar), implying n = ans - 1.
        return ans - 1;
    }

    // --- Phase 2: Solve for large n ---
    // Construct a stride-based query vector
    std::vector<long long> large_query;
    large_query.reserve(K);
    for (int i = 1; i <= K; ++i) {
        large_query.push_back(i * STRIDE);
    }

    // Randomized Divide & Conquer to isolate a colliding pair
    std::mt19937 rng(1337); 
    std::shuffle(large_query.begin(), large_query.end(), rng);

    std::vector<long long> current_set = large_query;
    
    // Narrow down to a pair
    while (current_set.size() > 2) {
        int n_size = current_set.size();
        int mid = n_size / 2;
        
        // Split set into Left and Right
        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());
        
        // Greedily recurse into a half that contains collisions
        if (collisions(left_part) > 0) {
            current_set = left_part;
            continue;
        }
        
        if (collisions(right_part) > 0) {
            current_set = right_part;
            continue;
        }
        
        // If neither half has collisions, but the parent set did, the collisions
        // are "crossing" (one element in Left, one in Right).
        // Reshuffle the parent set to attempt a different split.
        std::shuffle(current_set.begin(), current_set.end(), rng);
    }
    
    // We now have a small set (size 2) containing a collision
    long long val1 = current_set[0];
    long long val2 = current_set[1];
    long long diff = std::abs(val1 - val2);
    
    // n must be a divisor of this difference
    std::vector<long long> candidates = get_divisors(diff, SMALL_LIMIT);
    
    for (long long cand : candidates) {
        // Verify the candidate. 
        // If n = cand, then 1 and cand+1 will map to the same bucket (1 mod n).
        // Since we iterate from smallest divisor, the first valid one is n.
        std::vector<long long> verify_q = {1, cand + 1};
        if (collisions(verify_q) > 0) {
            return (int)cand;
        }
    }
    
    return -1; // Should not be reached
}

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