제출 #1317218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317218		jesusarg	Hack (APIO25_hack)	C++20	99.90 / 100	61 ms	1820 KiB

hack

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define f first
#define s second
#define sz size()
using namespace std;

ll collisions(vector<ll> x);

bool ask(const vector<ll>& v, const vector<ll>& u){
    vector<ll> q;
    q.reserve(v.sz+u.sz);
    for(auto i:v){q.pb(i);}
    for(auto i:u){q.pb(i);}
    ll k = collisions(q);
    return k>0;
}

ll solve(ll x) {
    ll n=x, di=x;
    for(ll p=2; p*p <= di; p++){
        while(di%p==0){
            ll cand=n/p;
            if(n%p==0 && cand>=2 && collisions({1, cand+1})>0){
                n/=p;
            }
            di/=p;
        }
    }
    ll cand=n/di;
    if(n%di==0 && di>1){
        if(collisions({1,cand+1}) > 0)
            n=cand;
    }
    return n;
}
int hack(){
    ll mx=(ll)(1e9);
    const int b = 15013;
    vector<ll> v,u;
    for(int i = 1; i <= b; i++){
        v.pb(i);
    }
    for(ll x = ((mx>>1)/b)*b; x <= mx+b; x+=b){
        u.push_back(x);
    }
    while(v.sz > 1 || u.sz > 1){
        if(v.sz < u.sz){
            swap(v,u);
        }
        int mid=(v.sz>>1);
        vector<ll> l(v.begin(),v.begin()+mid);
        vector<ll> r(v.begin()+mid,v.end());
        if(ask(l,u)){
            v.swap(l);
        }else{
            v.swap(r);
        }
    }
    //return llabs(v[0]-u[0]); -> es multiplo pero no necesariamente n 
    return solve(llabs(v[0]-u[0]));
}

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