Submission #1216324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216324		anfi	Hack (APIO25_hack)	C++20	100 / 100	109 ms	964 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
const long long inf = 1e9;

int ans(int l, int r) {
    while (l < r) {
        int m = (l + r) >> 1;
        int c = sqrtl(m - l + 1);
        vector<int> q;
        for (int i = 1; i <= c; ++i) q.push_back(i);
        for (int i = l + c; i <= m; i += c) q.push_back(i);
        if (m + 1 > c) q.push_back(m + 1);
        if (collisions(q)) {
            r = m;
        } else {
            l = m + 1;
        }
    }

    vector<int> divs;
    divs.push_back(l);
    for (int i = 2; i * i <= l; ++i) {
        if (l % i == 0) {
            divs.push_back(i);
            if (i * i != l) divs.push_back(l / i);
        }
    }
    sort(divs.begin(), divs.end());

    vector<int> primes;
    for (int d : divs) {
        bool is_prime = true;
        for (int p : primes) {
            if (d % p == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) primes.push_back(d);
    }

    int prev_l = -1;
    while (l != prev_l) {
        prev_l = l;
        for (int p : primes) {
            if ((l / p) * p == l) {
                if (collisions({1, (l / p) + 1})) {
                    l /= p;
                    break;
                }
            }
        }
    }
    return l;
}

signed hack() {
    return ans(inf / 2, inf);
}

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