Submission #1210915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210915		sqrtxsunlight	Hack (APIO25_hack)	C++20	98.60 / 100	55 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;
    while (dif > -1)
    {
        int d = sqrt (dif + 1);
        if (dntm (l, d, d)) return true;
        l += d * d;
        dif -= d * d;
    }

    return false;
}

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.5512 / 75