Submission #1285294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285294		goulthen	Hack (APIO25_hack)	C++20	25 / 100	43 ms	1536 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define pb push_back

int closest_prime(int x) {
    per(j,x,1) {
        bool ok = 1;
        for(int i = 2; i*i <= j; ++i) {
            if(j%i==0) {
                ok=0;
                break;
            }
        }
        if(ok) return j;
    }
    return -1;
}

int hack(){
    vector<ll> vals;
    ll B = 31627, b = 31627;
    ll N = 1000000000;
    ll l = 1,r,x;
    while (1) {
        vals.clear();
        for(ll i = 1; i<=b; i++) {
            vals.pb(i);
        }
        for(ll i = N+1; i<=N+b*b+1; i+=b) {
            vals.pb(i);
        }

        x = collisions(vals);
        //cout << x << '\n';

        if(x>B) {
            l=1;
            break;
        }

        int L=b*b/(x+1),R=b*b/(x);
        if(x==1) R = N;
        //cout << L << ' ' << R << ' ' << x << ' ' << l << '\n';
        l += L;
        b = closest_prime(sqrt(b*b/2));
        if(R-L+1 <= 2*B) break;
    }

    
    //cout << "FOUND RANGE: " << l << ' ' << l+B << '\n';
    for(ll i = l ; i <= l+2*B; i++) {
        if(i==0)continue;
        x = collisions({2*i,i});
        if(x==1) {
            return i;
        }
    }

    for(ll i = B; i<= N; i+=B) {
        x = collisions({2*i,i});
        if(x==1) {
            return i;
        }
    }

    return -1;
}

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