Submission #1208087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208087		thunopro	Hack (APIO25_hack)	C++20	63.60 / 100	91 ms	2532 KiB

hack

#include "hack.h"
#include<bits/stdc++.h>
using namespace std; 
// collisions
#define get collisions
#define ll long long 
#define re exit (0); 
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 ; 
}

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> Left , Right1 , Right2 ; 
        for ( int i = 0 ; i < A.size()/2 ; i ++ ) Left . push_back (A[i]) ; 
        for ( int i = A.size()/2 ; i < A.size()/2 + A.size()/4 ; i ++ ) Right1 . push_back (A[i]) ; 
        for ( int i = A.size()/2 + A.size()/4 ; i < A.size () ; i ++ ) Right2 . push_back (A[i]) ; 
        if ( get (merge(Left,Right1)) ) A = merge (Left,Right1) ; 
        else if ( get (merge(Right1,Right2))) A = merge (Right1,Right2) ; 
        else A = merge ( Left , 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: 38.561 / 75