Submission #1224154

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

hack

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

int hack() {
    ll l = 5e8 - 1, r = 1e9 + 1;

    while(l + 1 < r) {
        ll m = (l+r)/2;
        // check if its in [l, m]
        ll s = sqrt(m-l+1);
        vector<ll> send;
        for(ll i = 1; i <= s; i++) send.push_back(i);
        ll right = m+1;
        while(right > s) {
            send.push_back(right);
            if(right - s <= l) break;
            right -= s;
        }

        if(collisions(send) > 0) r = m;
        else l = m;
    }

    ll ans = r;

    auto test = [&](int x){
        while(true) {
            if(ans % x != 0) return;
            ans /= x;
            if(collisions({1, ans+1}) == 0) {
                ans *= x;
                return;
            }
        }
    };

    ll p = 2;

    while(p*p <= r) {
        if(r % p == 0) {
            while(r % p == 0) r /= p;
            test(p);
        }
        p++;
    }
    
    if(r > 1) test(r);

    return ans;
}

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