Submission #1210918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210918		sqrtxsunlight	Hack (APIO25_hack)	C++20	98.70 / 100	63 ms	964 KiB

hack

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

bool dntm (int l, int a, int b)
{
    vector <long long> v_ask;
    for (int i = 1; i <= a; i ++) v_ask.push_back (i);
    for (int i = a + l; i <= a * b + l; i += a) v_ask.push_back (i);

    return collisions (v_ask);
}

bool check_inside (int l, int r)
{
    int dif = r - l, d = sqrt (dif + 1);
    if (dntm (l, d, d)) return true;
    dif -= d * d;
    if (dif < 0) return false;

    d = sqrt (dif) + 1;
    return dntm (r - d * d + 1, d, d);
}

int hack()
{
    int le = 5e8, ri = 1e9;
    while (le < ri)
    {
        int mid = (le + ri) / 2;

        if (check_inside (le, mid)) ri = mid;
        else le = mid + 1;
    }

    vector <int> divs;
    for (int i = 2; i * i < le; i ++)
    {
        if (le % i == 0)
        {
            divs.push_back (i);
            divs.push_back (le / i);
        }
    }

    sort (divs.begin (), divs.end ());
    for (auto i: divs)
    {
        if (i == 1) continue;
        if (dntm (i, 1, 1)) return i;
    }

    return le;
}

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