Submission #1209597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209597		khanhphucscratch	Hack (APIO25_hack)	C++20	52.70 / 100	367 ms	6152 KiB

hack

#include "hack.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ansn, debug = 0;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int rnd(int l, int r)
{
    int x = rng()%(r-l+1);
    return x+l;
}
/*int collisions(vector<int> a)
{
    map<int, int> f; debug += a.size();
    for(int i : a) f[i%ansn]++;
    int ans = 0;
    for(pair<int, int> i : f) ans += i.second * (i.second-1)/2;
    return ans;
}*/
vector<int> concat(vector<int> a, vector<int> b)
{
    for(int i : b) a.push_back(i);
    return a;
}
pair<int, int> find_collision_bipartite(vector<int> a, vector<int> b)
{
    shuffle(a.begin(), a.end(), rng);
    shuffle(b.begin(), b.end(), rng); //Pray for some luck
    if(a.size() == 1 && b.size() == 1){
        //cerr<<"A"<<a.size()<<" "<<b.size()<<" "<<a[0]<<" "<<b[0]<<endl;
        return {a[0], b[0]};
    }
    vector<int> a0, a1, b0, b1;
    for(int i = 0; i < a.size(); i++){
        if(i < a.size()/2) a0.push_back(a[i]);
        else a1.push_back(a[i]);
    }
    for(int i = 0; i < b.size(); i++){
        if(i < b.size()/2) b0.push_back(b[i]);
        else b1.push_back(b[i]);
    }
    if(collisions(concat(a, b0)) > 0){
        if(collisions(concat(a0, b0)) > 0) return find_collision_bipartite(a0, b0);
        else return find_collision_bipartite(a1, b0);
    }
    else{
        if(collisions(concat(a0, b1)) > 0) return find_collision_bipartite(a0, b1);
        else return find_collision_bipartite(a1, b1);
    }
}
pair<int, int> find_collision_pair(vector<int> question)
{
    shuffle(question.begin(), question.end(), rng); //Pray for some luck
    if(question.size() == 2) return {question[0], question[1]};
    int mid = (question.size()-1)/2;
    vector<int> le, ri;
    for(int i = 0; i < question.size(); i++){
        if(i <= mid) le.push_back(question[i]);
        else ri.push_back(question[i]);
    }
    if(collisions(le) > 0) return find_collision_pair(le);
    if(collisions(ri) > 0) return find_collision_pair(ri);
    return find_collision_bipartite(le, ri);
}
int32_t hack()
{
    //Subtask 1;
    vector<int> question;
    const int iteration = 50000;
    set<int> st;
    while(st.size() < iteration) st.insert(rnd(1, 1e12));
    for(int i : st) question.push_back(i);
    while(collisions(question) == 0){
        question.clear(); st.clear();
        for(int i = 1; i <= iteration; i++){
            int x = rnd(1, 1e12);
            if(st.count(x) == 0){
                st.insert(x);
                question.push_back(x);
            }
        }
    }
    //cerr<<"A"<<debug<<endl;
    pair<int, int> a = find_collision_pair(question);
    int dif = abs(a.first - a.second);
    //cerr<<"A"<<a.first<<" "<<a.second<<endl;
    vector<int> candidate;
    for(int i = 1; i * i <= dif; i++) if(dif%i == 0){
        candidate.push_back(i);
        if(i*i < dif) candidate.push_back(dif/i);
    }
    sort(candidate.begin(), candidate.end());
    for(int i : candidate) if(collisions({i, 2*i}) == 1) return i;
    return -1; //This shouldn't happen
}
/*signed main()
{
    int sum = 0;
    for(int test = 1; test <= 10; test++){
        ansn = 1e9; debug = 0;
        cerr<<hack()<<endl;
        sum = max(sum, debug);
    }
    cerr<<sum<<endl;
}
*/

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