제출 #1294688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294688		ChottuF	Hack (APIO25_hack)	C++20	100 / 100	67 ms	2084 KiB

hack

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

const vector<int> PRIMES = {
    27361, 27367, 27397, 27407, 27409, 27427, 
    27431, 27437, 27449, 27457, 27479, 27481,
    27487, 27509, 27527, 27529, 27539, 27541
};

//const long long BB = 22993;
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(){
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> dist(0, PRIMES.size() - 1);
    const long long BB = PRIMES[dist(rng)];
    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: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 75 / 75