Submission #1256219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256219		biank	Hack (APIO25_hack)	C++20	100 / 100	81 ms	964 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)

#define sz(x) (int) x.size()
#define all(x) begin(x), end(x)

using namespace std;

#define pb push_back

using ll = long long;
using vi = vector<int>;

bool query(ll l, ll r) {
    ll base = sqrt(r - l + 1);
    vector<ll> v;
    forsn(i, 1, base + 1) v.pb(i);
    ll curr = base + l;
    while (curr <= r) {
        v.pb(curr);
        curr += base;
    }
    v.pb(r + 1);
    return collisions(v) != 0;
}

vector<ll> primes(ll n) {
    vector<ll> p;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) p.pb(i);
        while (n % i == 0) n /= i;
    }
    if (n != 1) p.pb(n);
    return p;
}

int hack() {
    ll lo = 5e8, hi = 1e9;
    while (hi - lo > 1) {
        ll mid = (lo + hi) / 2;
        if (query(lo + 1, mid)) hi = mid;
        else lo = mid;
    }
    for (ll p : primes(hi)) {
        while (hi % p == 0) {
            if (collisions(vector<ll>{(hi / p), 2 * (hi / p)})) hi /= p;
            else break;
        }
    }
    return hi;
}

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