Submission #1204841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204841		model_code	Hack (APIO25_hack)	C++20	66.40 / 100	123 ms	4560 KiB

hack

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

using namespace std;

map<vector<long long>, long long> memo;
long long ask(vector<long long> x){
    sort(x.begin(), x.end());
    if (memo.find(x) != memo.end()){
        return memo[x];
    }
    return memo[x] = collisions(x);
}

vector<long long> merge(vector<long long> vl, vector<long long> vr){
    vector<long long> res = vl;
    res.insert(res.end(), vr.begin(), vr.end());
    return res;
}

long long solve(vector<long long> A, vector<long long> B){
    int szA = (int) A.size(), szB = (int) B.size();
    if (szA == 1 && szB == 1) return llabs(A[0] - B[0]);

    if (szA < szB){
        swap(A, B);
        swap(szA, szB);
    }

    vector<long long> L(A.begin(), A.begin() + szA / 2);
    vector<long long> R(A.begin() + szA / 2, A.end());

    long long cnt = ask(merge(L, B));
    cnt -= ask(L);
    cnt -= ask(B);

    if (cnt > 0){
        return solve(L, B);
    } else {
        return solve(R, B);
    }
}

int hack(){
    int L = 22370;
    memo.clear();
    
    vector<long long> A;
    for (int i = 1; i <= L; i++){
        A.push_back(i);
    }

    vector<long long> B;
    for (int i = 1; i <= L; i++){
        int mid = (int)5e8;
        B.push_back(mid + i * L);
    }

    long long n = solve(A, B);

    long long m = n;

    vector<pair<long long, int>> primes;
    for (long long p = 2; p * p <= m; p++){
        int q = 0;
        while (m % p == 0){
            m /= p;
            q++;
        }
        if (q) primes.emplace_back(p, q);
    }

    if (m != 1){
        primes.emplace_back(m, 1);
    }

    for (auto [p, q] : primes){
        while (q--){
            if (ask({1, n / p + 1}) == 0) break;
            n /= p;
        }
    }

    return n;
}

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