Submission #1253552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253552		noop	Hack (APIO25_hack)	C++20	0 / 100	2 ms	1864 KiB

hack

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

bool query (const vector<long long>& a, const vector<long long>& b) {
    vector<long long> v;
    v.reserve(a.size()+b.size());
    for (size_t i=0; i<a.size(); ++i)
        v.push_back(a[i]);
    for (size_t i=0; i<b.size(); ++i)
        v.push_back(b[i]);
    return collisions(v);
}

void factor (long long x, vector<long long>& v) {
    vector<long long> ret;
    long long i=2;
    while (i*i<=x){
        if (!(x%i)){
            v.push_back(i);
            x/=i;
        }
        else
            ++i;
    }
    if (x>1)
        v.push_back(x);
}

int hack(){
    constexpr long long gap=31623;
    vector<long long> a,b;
    a.reserve(gap);
    b.reserve(gap);
    for (long long i=1; i<=gap; ++i)
        a.push_back(i);
    for (long long i=gap*(500000000/gap); i<=1000000000; i+=gap)
        b.push_back(i);
    while (a.size() || b.size()){
        vector<long long> l,r;
        if (a.size()>b.size()){
            l.reserve(a.size()>>1);
            r.reserve((a.size()>>1)+(a.size()&1));
            for (size_t i=0; i<a.size()>>1; ++i)
                l.push_back(a[i]);
            for (size_t i=b.size()>>1; i<a.size(); ++i)
                l.push_back(a[i]);
            if (query(l,b))
                a=l;
            else
                a=r;
        }
        else{
            l.reserve(b.size()>>1);
            r.reserve((b.size()>>1)+(b.size()&1));
            for (size_t i=0; i<b.size()>>1; ++i)
                l.push_back(b[i]);
            for (size_t i=b.size()>>1; i<b.size(); ++i)
                l.push_back(b[i]);
            if (query(l,a))
                b=l;
            else
                b=r;
        }
    }
    long long d=b[0]-a[0];
    vector<long long> factors;
    factor(d,factors);
    for (size_t i=0; i<factors.size(); ++i){
        if (collisions({1,d/factors[i]+1}))
            d/=factors[i];
    }
    return d;
}

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