Submission #1246223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246223		radaiosm7	Hack (APIO25_hack)	C++20	37.10 / 100	147 ms	2772 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> x, y, di, xf, xf1, xf2, xs, xs1, xs2;
mt19937 mt(time(NULL));
int l, r, m, fe, se;
const int s = 50000;
const long long tw = 1000000000000LL;

int hack(){
    while (true) {
        x.clear();
        for (int i=0; i < s; ++i) x.push_back(mt()%tw+1LL);
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());
        if (collisions(x) != 0) break;
    }


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

        if (collisions(xf) != 0) {
            x = xf;
            continue;
        }

        if (collisions(xs) != 0) {
            x = xs;
            continue;
        }

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

        if (mt() & 1) swap(xf1, xf2);
        if (mt() & 1) swap(xs1, xs2);
        y.clear();
        for (auto el : xf1) y.push_back(el);
        for (auto el : xs1) y.push_back(el);
        if (collisions(y) != 0) {
            x = y;
            continue;
        }

        y.clear();
        for (auto el : xf2) y.push_back(el);
        for (auto el : xs1) y.push_back(el);
        if (collisions(y) != 0) {
            x = y;
            continue;
        }

        y.clear();
        for (auto el : xf1) y.push_back(el);
        for (auto el : xs2) y.push_back(el);
        if (collisions(y) != 0) {
            x = y;
            continue;
        }

        y.clear();
        for (auto el : xf2) y.push_back(el);
        for (auto el : xs2) y.push_back(el);
        x = y;
    }

    long long diff = x[1]-x[0];

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

    di.push_back(diff);
    sort(di.begin(), di.end());
    di.erase(unique(di.begin(), di.end()), di.end());
    int l1 = 0;
    int r1 = (int)di.size()-1;
    int p1 = -1;

    while (l1 <= r1) {
        int m1 = (l1+r1)/2;
        y.clear();
        y.push_back(1LL);
        for (int i=l1; i <= m1; ++i) y.push_back(di[i]+1LL);
        if (collisions(y) == 0LL) l1 = m1+1;
        else {
            r1 = m1-1;
            p1 = di[m1];
        }
    }

    return p1;
}

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