Submission #1246468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246468		radaiosm7	Hack (APIO25_hack)	C++20	100 / 100	58 ms	1880 KiB

hack

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

const long long S = 27380;
const long long N = 1000000000;
vector<long long> xf, xs, xf1, xf2, xs1, xs2, y, di;
long long diff, nd;

int hack(){
    xf.clear();
    for(long long i=1; i <= S; ++i) xf.push_back(i);
    xs.clear();
    for(long long i=S*(N/2LL/S); i <= N+S; i += S) xs.push_back(i);

    while ((int)xf.size() > 1 || (int)xs.size() > 1) {
        if ((int)xf.size() <= (int)xs.size()) {
            int m = (int)xs.size();
            xs1.clear();
            for (int i=0; i < m/2; ++i) xs1.push_back(xs[i]);
            xs2.clear();
            for (int i=m/2; i < m; ++i) xs2.push_back(xs[i]);

            y.clear();
            for (auto el : xf) y.push_back(el);
            for (auto el : xs1) y.push_back(el);
            if (collisions(y) != 0) xs = xs1;
            else xs = xs2;
        }

        else {
            int m = (int)xf.size();
            xf1.clear();
            for (int i=0; i < m/2; ++i) xf1.push_back(xf[i]);
            xf2.clear();
            for (int i=m/2; i < m; ++i) xf2.push_back(xf[i]);

            y.clear();
            for (auto el : xf2) y.push_back(el);
            for (auto el : xs) y.push_back(el);
            if (collisions(y) != 0) xf = xf2;
            else xf = xf1;
        }
    }

    diff = llabs(xs[0]-xf[0]);
    di.clear();
    nd = diff;

    for (long long d=2LL; d*d <= diff; ++d) {
        while (nd % d == 0LL) {
            di.push_back(d);
            nd /= d;
        }
    }

    if (nd > 1) di.push_back(nd);
    sort(di.begin(), di.end());

    for (auto d : di) {
        diff /= d;
        if (collisions({1, diff+1}) == 0) diff *= d;
    }

    return diff;
}

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