제출 #1311427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311427		Lakshya108	Hack (APIO25_hack)	C++20	0 / 100	2 ms	836 KiB

hack

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

#define pb push_back

const int N = 1e9;
const int B = (int)sqrt(N);

int collision(vector<int> v){
    sort(v.begin(), v.end());
    for(int i=1;i<(int)v.size();i++)
        if(v[i]==v[i-1]) return 1;
    return 0;
}

vector<int> fac(int x){
    vector<int> p;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            p.pb(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) p.pb(x);
    return p;
}

int hack(){
    int mn=(N>>1)/B, mx=N/B;
    vector<int>a,b;
    a.reserve(mx-mn+5);
    b.reserve(B+5);

    for(int i=1,j=mx;j>mn;j--,i+=B) a.pb(i);
    int c=a.back()+mn*B+B;
    for(int i=1;i<=B;i++) b.pb(c+i);

    auto g=[&](const vector<int>&x,const vector<int>&y){
        vector<int> v;
        v.reserve(x.size()+y.size());
        for(int i:x) v.pb(i);
        for(int i:y) v.pb(i);
        return collision(v);
    };

    while(a.size()>1||b.size()>1){
        if(a.size()>b.size()){
            int m=a.size()/2;
            vector<int>l(a.begin(),a.begin()+m),r(a.begin()+m,a.end());
            a=g(b,r)?r:l;
        }else{
            int m=b.size()/2;
            vector<int>l(b.begin(),b.begin()+m),r(b.begin()+m,b.end());
            b=g(r,a)?r:l;
        }
    }

    int x=b[0]-a[0];
    for(int p:fac(x)){
        while(x%p==0){
            int y=x/p;
            if(collision({1,y+1})) x=y;
            else break;
        }
    }

    return x;
}

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