#!/usr/bin/perl

use strict;
use warnings;

my @ranges = 0;
push @ranges, $ranges[-1] + 1 + int rand 200 for 1..1_000_000;

my @tests = map int rand $ranges[-1], 0..10_000_000;

match(0, scalar @ranges, 0, scalar @tests);

sub div {
    my ($border, $start, $end) = @_;
    while ($end > $start) {
        if ($tests[$start] < $border) {
            $start++;
        }
        else {
            if (--$end > $start) {
                @tests[$start, $end] = @tests[$end, $start];
            }
        }
    }
    $end;
}

sub match {
    my ($r_start, $r_end, $t_start, $t_end) = @_;
    if ($r_end - $r_start <= 1) {
        if ($t_end - $t_start > 0) {
            print "tests in range $ranges[$r_start]:\n", join(", ", @tests[$t_start..$t_end-1]), "\n";
        }
        else {
            print "range $ranges[$r_start] is empty\n";
        }
    }
    else {
        my $r_pivot = int(($r_start + $r_end)/ 2);
        my $t_pivot = div($ranges[$r_pivot], $t_start, $t_end);
        match($r_start, $r_pivot - 1, $t_start, $t_pivot - 1);
        match($r_pivot, $r_end, $t_pivot, $t_end);
    }
}