Submission #1208099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208099		thunopro	Hack (APIO25_hack)	C++20	62.90 / 100	84 ms	1872 KiB

hack

#include "hack.h"
#include<bits/stdc++.h>
using namespace std; 
// collisions
#define get collisions
#define ll long long 
#define re exit (0); 
#define pb push_back 
const int p = 27512 , q = 18175 , M = 5e8 ; 

vector<ll> merge ( vector <ll> Left , vector<ll> Right ) {
    vector<ll> res ; 
    for ( auto x : Left ) res . push_back (x) ; 
    for ( auto x : Right ) res . push_back (x) ; 
    return res ; 
}
mt19937 rng (time(0)) ; 
int hack(){
    vector<ll> A ;  
    for ( int i = 1 ; i <= p ; i ++ ) A . push_back (i) ; 
    for ( int i = 1 ; i <= q ; i ++ ) A . push_back (M+i*p) ; 
    int x ; 
    while ( A.size () > 2 ) 
    {
        vector <ll> left1 , left2 , right1, right2 ; 
        int N = A.size () ; 
        for ( int i = 0 ; i < N/4 ; i ++ ) left1 . pb (A[i]) ; 
        for ( int i = N/4 ; i < N/2 ; i ++ ) left2 . pb (A[i]) ; 
        for ( int i = N/2 ; i < N/2 + N/4 ; i ++ ) right1 . pb (A[i]) ;
        for ( int i = N/2 + N/4 ; i < N ; i ++ ) right2 . pb (A[i]) ; 
        if ( get (merge(left1,left2))) A = merge (left1,left2) ; 
        else if ( get (merge(right1,right2))) A = merge (right1,right2) ; 
        else 
        {
            if ( get (merge(left1,right1)) ) A = merge (left1,right1) ; 
            else if ( get (merge (left2,right1))) A = merge (left2,right1) ; 
            else if ( get (merge(left1,right2) )) A = merge (left1,right2) ; 
            else A = merge (left2,right2) ; 

        } 
        if ( A.size () == 2 ) 
        {
            x = abs (A[0]-A[1]) ; break ; 
        }
        if ( A.size () == 3 ) 
        {
            if ( get ({A[0],A[1]})) x = abs (A[0]-A[1]) ; 
            else if ( get ({A[0],A[2]})) x = abs (A[0]-A[2]) ; 
            else x = abs (A[1]-A[2]) ; 
            break ; 
        }
    }
    int w = x ; 
    for ( int i = 2 ; i*i <= x ; i ++ ) 
    {
        if ( x % i == 0 ) 
        {
            while ( w % i == 0 ) 
            {
                w /= i ; 
                if ( get ({1,1+w}) == 0 ) 
                {
                    w *= i ; break ; 
                } 
            }
        }
    }
    return w ; 
}

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