제출 #1317204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317204		jesusarg	Hack (APIO25_hack)	C++20	0 / 100	4 ms	1460 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);}
    return collisions(q)>0;
}

ll solve(ll n){
    for(ll p = 2; p*p <= n; p++){
        if(n%p != 0){
            continue;
        }
        while(n%p==0){
            ll c=n/p;
            if(collisions({1, c+1})>0){
                n=c;
            }else{
                break;  
            }
        }
    }
    return n;
}

int hack(){
    ll mx=(ll)(1e9);
    const int b = int(sqrt(1e9)-2);
    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: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 75