use strict; | |
use warnings; | |
# find the most greater value in range of less or equal to given target. | |
# returns the index of that value. | |
# array must be ascend sorted. | |
sub idx_of_max_in { | |
my ( $array, $head, $tail, $target ) = @_; | |
return $tail if $array->[$tail] <= $target; | |
return $head if $array->[$head] == $target; | |
while ( $head <= $tail ) { | |
my $where = int( ( $head + $tail ) / 2 ); | |
if ( $array->[$where] == $target ) { | |
return $where; | |
} | |
elsif ( $target < $array->[$where] ) { | |
$tail = $where - 1; | |
} | |
else { | |
$head = $where + 1; | |
} | |
} | |
return $head - 1; | |
} | |
my @lines = split "\n", do { local $/; <> }; | |
my ( $num_prices, undef ) = split( " ", shift(@lines) ); | |
my @prices = splice ( @lines, 0, $num_prices ); | |
sub array_based { | |
@prices = sort { $a <=> $b } @prices; | |
my $price_max_idx = $num_prices - 1; | |
my $min_price = $prices[0]; | |
my $min_pair_price = $prices[0] + $prices[1]; | |
my $binsearch_limit = $prices[0] + $prices[-1]; | |
my @results; | |
DAY: for my $target (@lines) { | |
$target = int($target); | |
# short cut for exceptional situation | |
if ( $min_pair_price > $target ) { | |
push @results, 0; | |
next DAY; | |
} | |
# find most expensive price in which cheeper than target price | |
# with using binary search | |
my ( $head, $tail ) = ( 0, $price_max_idx ); | |
if ( $target < $binsearch_limit ) { | |
$tail = idx_of_max_in( \@prices, $head, $tail, $target - $min_price ); | |
} | |
my $best = 0; | |
PRODUCT: while (1) { | |
my $tail_val = $prices[$tail]; | |
my $head_target = $target - $tail_val; | |
my ( $head_val, $head_next_val ) = ( $prices[$head], $prices[$head+1] ); | |
while ( $head_next_val <= $head_target && $head < $tail ) { | |
( $head_val, $head_next_val ) = ( $head_next_val, $prices[++$head] ); | |
} | |
my $val = $head_val + $tail_val; | |
if ( $best < $val && $val <= $target ) { | |
$best = $val; | |
last PRODUCT if $best == $target; | |
} | |
$tail--; | |
last PRODUCT unless $head < $tail; | |
} | |
push @results, $best; | |
} | |
my $res = join( "\n", @results ); | |
print $res, "\n"; | |
} | |
sub hist_based { | |
my @hist; | |
$hist[$_]++ for @prices; | |
my @low_ends; | |
for ( 0..500 ) { | |
push @low_ends, $_ if $hist[$_]; | |
} | |
my @results; | |
DAY: for my $target ( @lines ) { | |
my $tail = $target; | |
my $best = 0; | |
my $low_head = 0; | |
PRODUCT: while (1) { | |
do { $tail-- } while !$hist[$tail] && $tail; | |
last PRODUCT unless $tail; | |
my $head_target = $target - $tail; | |
last PRODUCT if $tail < $head_target; | |
next PRODUCT if $head_target == $tail && $hist[$tail] < 2; | |
if ( $head_target < $low_ends[-2] ) { | |
$low_head++ while $low_ends[$low_head + 1] <= $head_target; | |
my $head = $low_ends[$low_head]; | |
if ( $best < $head + $tail && $head + $tail <= $target) { | |
$best = $head + $tail; | |
last PRODUCT if $best == $target; | |
} | |
} | |
else { | |
my $head = $head_target; | |
$head-- while !$hist[$head] && $head; | |
next PRODUCT unless $head; | |
if ( $head + $tail > $target ) { | |
next PRODUCT; | |
} | |
if ( $best < $head + $tail ) { | |
$best = $head + $tail; | |
last PRODUCT if $best == $target; | |
} | |
} | |
} | |
push @results, $best; | |
} | |
my $res = join( "\n", @results ); | |
print $res, "\n"; | |
} | |
$num_prices > 10000 ? hist_based() : array_based(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment