Submission #1288715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288715		extraterrestrial	Hack (APIO25_hack)	C++20	0 / 100	6 ms	1204 KiB

hack

#include <bits/stdc++.h>
#include "hack.h"
using namespace std;

const int MAXN = 1e9;
const int B = sqrt(MAXN);

vector<int> factorize(int x) {
    assert(x > 1);
    vector<int> primes;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            primes.push_back(i);
            while (x % i == 0) {
                x /= i;
            }
        }
    }

    if (x > 1) {
        primes.push_back(x);
    }

    return primes;
}

int hack() {
    int mn = (MAXN / 2) / B, mx = MAXN / B;
    vector<int> big, small;
    int cur = 1;
    for (int i = mx; i > mn; i--) {
        big.push_back(cur);
        cur += B;
    }

    cur += mn * B;
    assert((cur - big[0]) / B == mx);
    for (int i = 1; i <= B; i++) {
        small.push_back(cur + i);        
    }

    auto good = [](const vector<int> &small, const vector<int> &big) {
        vector<long long> v;
        for (auto x : small) {
            v.push_back(x);
        }
        for (auto x : big) {
            v.push_back(x);
        }
        return collisions(v) > 0;
    };

    while (big.size() > 1 || small.size() > 1) {
        if (big.size() > small.size()) {
            int mid = big.size() / 2;
            auto big_left = vector<int>(big.begin(), big.begin() + mid);
            auto big_right = vector<int>(big.begin() + mid, big.end());
            if (good(big_left, small)) {
                big = big_left;
            } else {
                big = big_right;
            }
        } else {
            int mid = small.size() / 2;
            auto small_left = vector<int>(small.begin(), small.begin() + mid);
            auto small_right = vector<int>(small.begin() + mid, small.end());
            if (good(big, small_left)) {
                small = small_left;
            } else {
                small = small_right;
            }
        }
    }

    int x = small[0] - big[0];
    auto primes = factorize(x);

    for (auto p : primes) {
        while (x % p == 0) {
            int nxt = x / p;
            if (collisions({1, nxt + 1}) > 0) {
                x = nxt;
            } else {
                break;
            }
        }
    }

    return x;
}

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