제출 #1360112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360112		Aviansh	Hack (APIO25_hack)	C++20	27.30 / 100	1027 ms	27040 KiB

hack

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

using namespace std;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const long long inf = 1e14;
uniform_int_distribution<long long>ran(1,inf);

const int constant = 30000;

unordered_set<long long>curr;

void roll(vector<long long> &arr){
    int old = curr.size();
    curr.clear();
    while(curr.size()<old+constant){
        curr.insert(ran(rng));
    }
    arr.clear();
    for(long long i : curr){
        arr.push_back(i);
    }
}

int hack(){
    vector<long long>curr;
    roll(curr);
    while(collisions(curr)==0){
        roll(curr);
    }
    while(curr.size()>2){
        vector<long long>a,b;
        for(long long i : curr){
            if(rng()%2){
                a.push_back(i);
            }
            else{
                b.push_back(i);
            }
        }
        if(a.size()==0||b.size()==0)
            continue;
        if(a.size()>1&&collisions(a)){
            curr=a;
        }
        else if(b.size()>1&&collisions(b)){
            curr=b;
        }
        else{
            ///reroll
            continue;
        }
    }
    ///got distance
    assert(curr.size()==2);
    long long dist = abs(curr[1]-curr[0]);
    ///n is factor of dist
    set<long long>facs;
    for(int i = 2;1LL*i*i<=dist;i++){
        if(dist%i==0){
            facs.insert(i);
            facs.insert(dist/i);
        }
    }
    for(long long i : facs){
        assert(i<=1e9);
        if(collisions({1,1+i})){
            return i;
        }
    }
    return -1;
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 8 / 8
• 서브태스크 2: 17 / 17
• 서브태스크 3: 2.2535 / 75