Submission #1246162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246162		radaiosm7	Hack (APIO25_hack)	C++20	25 / 100	210 ms	708 KiB

hack

#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> x;
vector<long long> y;
vector<long long> di;
mt19937 mt(time(NULL));
int l, r, m, fe, se;
const int s = 10000;
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;
    }

    l = 0;
    r = (int)x.size()-1;
    fe = -1;

    while (l <= r) {
        m = (l+r)/2;
        y.clear();
        for (int i=0; i <= m; ++i) y.push_back(x[i]);
        if (collisions(y) == 0) l = m+1;
        else {
            r = m-1;
            fe = m;
        }
    }

    l = 0;
    r = fe-1;
    se = -1;

    while (l <= r) {
        m = (l+r)/2;
        y.clear();
        for (int i=m; i <= fe; ++i) y.push_back(x[i]);
        if (collisions(y) == 0) r = m-1;
        else {
            l = m+1;
            se = m;
        }
    }

    long long diff = x[fe]-x[se];

    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());
    int dsz = (int)di.size();

    for (int p=0; p < dsz; ++p) {
        vector<long long> v;
        v.push_back(1LL);
        v.push_back(di[p]+1LL);
        if (collisions(v) == 1) return di[p];
    }

    return 0;
}

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