Submission #1216317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216317		anfi	Hack (APIO25_hack)	C++20	0 / 100	32 ms	960 KiB

hack

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

const long long INF = 1e9;

int ans(int l, int r) {
    // Binary search untuk menemukan nilai minimum yang memicu collision
    while (l < r) {
        int m = (l + r) >> 1;
        int c = sqrtl(m - l + 1);
        vector<int> q;
        // Tambahkan titik awal
        for (int i = 1; i <= c; ++i) {
            q.push_back(i);
        }
        // Tambahkan sampel dari l + c hingga m dengan step c
        for (int x = l + c; x <= m; x += c) {
            q.push_back(x);
        }
        // Pastikan m+1 dicoba jika relevan
        if (m + 1 > c) {
            q.push_back(m + 1);
        }
        // Cek collision
        if (collisions(q)) {
            r = m;
        } else {
            l = m + 1;
        }
    }

    // Persiapan sieve hingga sqrt(l) untuk mendapatkan daftar prima
    int limit = sqrtl(l);
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    vector<int> primes;
    for (int i = 2; i <= limit; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            if ((long long)i * i <= limit) {
                for (int j = i * i; j <= limit; j += i) {
                    is_prime[j] = false;
                }
            }
        }
    }

    // Memurnikan hasil dengan membagi faktor prima selama memenuhi collision
    int prev = -1;
    while (l != prev) {
        prev = l;
        for (int p : primes) {
            if (l % p == 0) {
                if (collisions({1, l / p + 1})) {
                    l /= p;
                    break;
                }
            }
        }
    }
    return l;
}

signed hack() {
    return ans(INF / 2, INF);
}

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