Submission #1204859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204859		windowwife	Hack (APIO25_hack)	C++20	100 / 100	80 ms	964 KiB

hack

#ifndef rtgsp
#include "hack.h"
#endif // rtgsp

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1e6 + 4;
int t, n, x, op = 0;
vector<ll> v;
map<int, int> mp;

#ifdef rtgsp
ll collisions (vector<ll> x)
{
    op += x.size();
    ll res = 0;
    mp.clear();
    for (ll i : x)
        res += mp[i % n]++;
    return res;
}
#endif // rtgsp

int hack ()
{
    int l = 5e8 + 1, r = 1e9, m = 0;
    op = 0;
    while (l < r)
    {
        m = (l + r)/2;
        x = sqrt(m - l + 1);
        v.clear();
        for (int i = 1; i <= x; i++) v.push_back(i);
        for (int i = l + x; i <= m + x; i += x) v.push_back(min(i, m + 1));
        if (collisions(v)) r = m;
        else l = m + 1;
    }
    m = sqrt(r);
    for (int i = 2; i <= m; i++)
    {
        if (r % i == 0)
        {
            while (r % i == 0) r /= i;
            while (l % i == 0 && collisions({1, l/i + 1})) l /= i;
        }
    }
    if (r > 1 && l % r == 0 && collisions({1, l/r + 1})) l /= r;
    return l;
}

#ifdef rtgsp
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n;
        cout << hack() << " " << op << endl;
    }
}
#endif // rtgsp

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