Submission #1204992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204992		Kel_Mahmut	Hack (APIO25_hack)	C++20	68 / 100	139 ms	1308 KiB

hack

#include "hack.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

const int N = 1e9;
const int N2 = 5e8;
const int k = 7700;
const int b2 = N2 / k;
const int b = N / k;

int hack(){
    vector<ll> s(k);
    for(int i = 0; i < k; i++) s[i] = i + 1;
    function<ll(int, int)> get = [&](int tl, int tr){
        vector<ll> r;
        for(int i = tl; i <= tr; i++){
            if((i + 1) * k <= k) continue;
            r.pb((i + 1) * k);
        }
        for(int i : s) r.pb(i);
        return collisions(r);
    };
    function<int(int)> fin_get = [&](int x){
        // [x * k, x * (k + 1))
        int tl = 1, tr = k;
        while(tr > tl){
            // cout << tl << ' ' << tr << ' ';
            int tm = (tl + tr + 1) / 2;
            vector<ll> r = {k * (x + 1)};
            for(int i = tm; i <= tr; i++){
                if(k * (x + 1) <= i) continue;
                r.pb(i);
            }
            ll ok = collisions(r);
            // cout << ok << endl;
            if(ok)
                tl = tm;
            else
                tr = tm - 1;
        }
        return (x + 1) * k - tl;
    };
    int tl = b2, tr = b;
    while(tl < tr){
        int tm = (tl + tr) / 2;
        if(get(tl, tm))
            tr = tm;
        else
            tl = tm + 1;
    }
    int ans = fin_get(tl);
    int res = ans;
    for(int i = 2; i * i <= ans; i++){
        while(ans % i == 0){
            if(collisions({1ll, res / i + 1})){
                ans /= i;
                res /= i;
            }
            else
                break;
        }
        while(ans % i == 0){
            ans /= i;
        }
    }
    if(ans > 1 && collisions({1ll, (ll) res / ans + 1}))
        res /= ans;
    return res;
}

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