Submission #1210925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210925		sqrtxsunlight	Hack (APIO25_hack)	C++20	100 / 100	54 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;
    int d = sqrt (dif + 1);

    if (d * (d + 1) > dif + 1)
    {
        if (dntm (l, d, d)) return true;
        dif -= d * d;
    }
    else
    {
        if (dntm (l, d, d + 1)) return true;
        dif -= d * (d + 1);
    }

    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 ());
    divs.push_back (le);

    int l = 0, r = divs.size () - 1;
    while (l < r)
    {
        int mid = (l + r) / 2;
        vector <long long> v_ask = {1};
        for (int i = l; i <= mid; i ++) v_ask.push_back (divs[i] + 1);

        //for (auto i: v_ask) cout << i << ' ';
        //cout << '\n';

        if (collisions (v_ask)) r = mid;
        else l = mid + 1;
    }

    return divs[l];
}

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