Submission #1294674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294674		ChottuF	Hack (APIO25_hack)	C++20	0 / 100	4 ms	1632 KiB

hack

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

const long long BB = 27380;
const long long MAXN = 1e9;


bool query(vector<long long> A, vector<long long> B){
    for (auto u : B) A.push_back(u);
    for (auto u : A){
        //cout << u << " ";
    }
    //cout << '\n';
    long long x = collisions(A);
    return (x > 0);
}

int hack(){
    vector<long long> A,B;
    for (long long i = 1; i<=BB; i++){
        A.push_back(i);
    }
    for (long long st = ((MAXN/2)/BB)*BB; st <= MAXN+(BB*10); st += BB){
        B.push_back(st);
    }
    
    while (A.size() > 1 || B.size() > 1){
        if (A.size() <= B.size()) swap(A,B); //ensures A is bigger
        //split A
        vector<long long> fst,scd;
        for (long long i = 0; i<A.size(); i++){
            if (i < A.size()/2) fst.push_back(A[i]);
            else scd.push_back(A[i]);
        }
        if (query(fst, B)){
            //it's inside here
            A.clear();
            for (auto u : fst) A.push_back(u);
        }
        else{
            A.clear();
            for (auto u : scd) A.push_back(u);
        }
    }
    long long one = A[0];
    long long two = B[0];
    long long dif = abs(one-two);
    
    vector<long long> fac;
    long long diff = dif;
    for (long long i = 2; i*i <= diff; i++){
        while (diff % i == 0){
            fac.push_back(i);
            diff /= i;
        }
    }
    if (diff > 1) fac.push_back(diff);
    
    for (auto u : fac){
        vector<long long> tst = {1, (dif/u)+1};
        if (collisions(tst)){
            dif /= u;
        }
    }
    return dif;
}

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