Submission #1246421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246421		radaiosm7	Hack (APIO25_hack)	C++20	80.60 / 100	68 ms	1808 KiB

hack

//chockolateman credit
#include<bits/stdc++.h>
#include <vector>
#include "hack.h"

using namespace std;

const long long S = 31623;
const long long N = 1000000000;


vector<long long> nums;
vector<long long> temp;

long long query_pair(int x)
{
    temp.clear();
    temp.push_back(1);
    temp.push_back(1+x);
    return collisions(temp);
}

long long many(long long k) {
    long long res = 0LL;
    for (long long l=1; l <= S; ++l) res += (l-1)/k;
    return res;
}

int hack(){
    vector<long long> xf,xs,xs1,xs2,y;

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

    long long quer = collisions(xf);
    if (quer != 0LL) {
        long long l = 2LL;
        long long r = S;

        while (l < r) {
            long long m = (l+r)/2LL;
            long long v = many(m);
            if (v == quer) {
                l = m;
                break;
            }

            else if (v < quer) r = m-1;
            else l = m+1;
        }

        return l;
    }

    while ((int)xf.size() > 1 || (int)xs.size() > 1) {
        if ((int)xf.size() > (int)xs.size()) swap(xf, xs);

        xs1.clear();
        xs2.clear();
    
        int 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]);

        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;
    }

    long long diff = llabs(xs[0]-xf[0]);

    vector<long long> di;
        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];
    }
}

Compilation message (stderr)

hack.cpp: In function 'int hack()':
hack.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
   95 | }
      | ^

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