Submission #1311429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311429		Lakshya108	Hack (APIO25_hack)	C++20	98.40 / 100	66 ms	1644 KiB

hack

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

using ll = long long;

const ll B = 22303;
const ll N = 1e9;

inline bool q(vector<ll> a, const vector<ll>& b){
    a.insert(a.end(), b.begin(), b.end());
    return collisions(a) > 0;
}

int hack(){
    vector<ll> a, b;
    for(ll i=1;i<=B;i++) a.push_back(i);
    for(ll x=((N/2)/B)*B;x<=N+B;x+=B) b.push_back(x);

    while(a.size()>1 || b.size()>1){
        if(a.size()<=b.size()) swap(a,b);
        int m=a.size()/2;
        vector<ll> l(a.begin(),a.begin()+m), r(a.begin()+m,a.end());
        a = q(l,b) ? l : r;
    }

    ll x = llabs(a[0]-b[0]), t=x;
    for(ll p=2;p*p<=t;p++){
        while(t%p==0){
            if(collisions({1,x/p+1})) x/=p;
            t/=p;
        }
    }
    if(t>1 && collisions({1,x/t+1})) x/=t;

    return x;
}

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