Submission #1246319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246319		KALARRY	Hack (APIO25_hack)	C++20	0 / 100	1670 ms	1114112 KiB

hack

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

using namespace std;


int counter = 0;

vector<int> nums;
vector<long long> temp;

long long query_pair(int x)
{
    temp.clear();
    temp.push_back(1);
    temp.push_back(1+x);
    counter += 2;
    return collisions(temp);
}

int hack(){
    counter = 0;
    temp.clear();
    if(nums.empty())
    {
        nums.push_back(0); //make it 1-indexed
        int S = 31623;
        while(S = 1)
        {
            for(int i = 1 ; i <= S ; i++)
                nums.push_back(nums.back() + S);
            int want_to_build = S - 1;
            S = 0;
            while(S*S < want_to_build)
                S++;
        }
        nums.push_back(1);
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(nums.begin()+1, nums.end(), rng);

    int l = 1;
    int r = nums.size() - 1;
    int last_push = 0;
    while(l < r)
    {
        int mid = (l+r+1)/2;
        for(int i = last_push + 1 ; i <= mid ; i++)
            temp.push_back(nums[i]);
        for(int i = last_push ; i > mid ; i--)
            temp.pop_back();
        last_push = mid;
        long long res = collisions(temp);
        counter += temp.size();
        // assert(counter <= 900000);
        if(res)
            r = mid-1;
        else
            l = mid;
    }
    r++;
    int n;
    for(l = r-1 ; l >= 0 ; l--)
        if(query_pair(abs(nums[r] - nums[l])))
        {
            n = abs(nums[r] - nums[l]);
            break;
        }
    vector<int> div;
    for(int x = 1 ; x*x <= n ; x++)
        if(n%x==0)
        {
            div.push_back(x);
            int y = n/x;
            if(y != x)
                div.push_back(y);
        }
    sort(div.begin(),div.end());
        for(auto x : div)
            if(x != n && query_pair(x))
            {
                n = x;
                break;
            }
    return n;
}

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