Submission #1246131

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246131		KALARRY	Hack (APIO25_hack)	C++20	25 / 100	463 ms	10640 KiB

hack

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

using namespace std;

const long long S = 31600;

vector<long long> nums;

bool done[1000005];
long long memo[1000005];

long long query_pair(long long x)
{
    if(done[x])
        return memo[x];
    done[x] = true;
    vector<long long> temp;
    temp.push_back(1);
    temp.push_back(1+x);
    memo[x] = collisions(temp);
    return memo[x];
}


long long query(long long l,long long r)
{
    vector<long long> temp;
    for(long long i = l ; i <= r ; i++)
        temp.push_back(nums[i]);
    long long res = collisions(temp);
    return res;
}

long long counter = 0;

int hack(){
    counter++;
    memset(done,false,sizeof(done));
    memset(memo,0ll,sizeof(memo));
    if(nums.empty())
    {
        nums.push_back(0); //make it 1-indexed
        for(long long i = 1 ; i < S ; i++)
            nums.push_back(nums.back() + 1);
        for(long long i = 1 ; i <= S ; i++)
            nums.push_back(nums.back() + S);
    }
    long long l = 1;
    long long r = nums.size() - 1;
    while(l < r)
    {
        long long mid = (l+r+1)/2;
        if(query(1,mid))
            r = mid-1;
        else
            l = mid;
    }
    long long r_num = r+1;
    l = 1;
    r = r_num;
    while(l < r)
    {
        long long mid = (l+r+1)/2;
        if(query(mid,r_num))
            l = mid;
        else
            r = mid-1;
    }    
    long long n = nums[r_num] - nums[l];
    vector<long long> temp;
    for(long long x = 1 ; x <= n ; x++)
        if(n%x==0)
        {
            temp.clear();
            temp.push_back(1);
            temp.push_back(1 + x);
            if(query_pair(x))
                n = x;
        }
    return n;
}

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