prompt:
Sleeping bodies report residual motion and wake-up comparisons drift.

solve(v, omega, lin_damp, ang_damp, dt, max_speed, sleep_lin, sleep_ang, sleep_time, kicks): per frame, a sleeping body wakes (timer reset) only when that frame's kick is nonzero, else it is skipped. Add the kick [dvx,dvy,domega], damp with 1/(1+dt*c) (linear and angular coefficients), clamp speed magnitude, then accumulate sleep time while |v|<sleep_lin and |omega|<sleep_ang (else reset). When timer>=sleep_time the body sleeps and velocities are zeroed. Return [vx, vy, omega, timer, asleep, frame index slept or -1].

split: open-access


meaning: Fixture-count band, not measured model difficulty

deps: stdlib

prompt:
Bodies sleep one frame late relative to the contract.

solve(v, omega, lin_damp, ang_damp, dt, max_speed, sleep_lin, sleep_ang, sleep_time, kicks): per frame, a sleeping body wakes (timer reset) only when that frame's kick is nonzero, else it is skipped. Add the kick [dvx,dvy,domega], damp with 1/(1+dt*c) (linear and angular coefficients), clamp speed magnitude, then accumulate sleep time while |v|<sleep_lin and |omega|<sleep_ang (else reset). When timer>=sleep_time the body sleeps and velocities are zeroed. Return [vx, vy, omega, timer, asleep, frame index slept or -1].

split: open-access


prompt:
The measured period is half the true oscillation period.

solve(xs, dt, omega): integrator frequency diagnostic. Upward crossings are samples with x[i-1]<0<=x[i], timed by linear interpolation. Period is the mean interval (last-first)/(count-1); relative error vs 2*pi/omega. Fewer than two crossings gives [None, count, None]. Return [period, count, error] rounded to 6.

split: open-access


prompt:
Crossing times jitter by up to one sample and the period estimate is noisy.

solve(xs, dt, omega): integrator frequency diagnostic. Upward crossings are samples with x[i-1]<0<=x[i], timed by linear interpolation. Period is the mean interval (last-first)/(count-1); relative error vs 2*pi/omega. Fewer than two crossings gives [None, count, None]. Return [period, count, error] rounded to 6.

split: open-access


prompt:
The period is underestimated by a factor (n-1)/n.

solve(xs, dt, omega): integrator frequency diagnostic. Upward crossings are samples with x[i-1]<0<=x[i], timed by linear interpolation. Period is the mean interval (last-first)/(count-1); relative error vs 2*pi/omega. Fewer than two crossings gives [None, count, None]. Return [period, count, error] rounded to 6.

split: open-access


prompt:
Relative error is dominated by a 2*pi factor.

solve(xs, dt, omega): integrator frequency diagnostic. Upward crossings are samples with x[i-1]<0<=x[i], timed by linear interpolation. Period is the mean interval (last-first)/(count-1); relative error vs 2*pi/omega. Fewer than two crossings gives [None, count, None]. Return [period, count, error] rounded to 6.

split: open-access


prompt:
A lagging integrator is reported as leading.

solve(xs, dt, omega): integrator frequency diagnostic. Upward crossings are samples with x[i-1]<0<=x[i], timed by linear interpolation. Period is the mean interval (last-first)/(count-1); relative error vs 2*pi/omega. Fewer than two crossings gives [None, count, None]. Return [period, count, error] rounded to 6.

split: open-access


prompt:
Sampled trajectories with exact zeros report missing periods.

solve(xs, dt, omega): integrator frequency diagnostic. Upward crossings are samples with x[i-1]<0<=x[i], timed by linear interpolation. Period is the mean interval (last-first)/(count-1); relative error vs 2*pi/omega. Fewer than two crossings gives [None, count, None]. Return [period, count, error] rounded to 6.

split: open-access


prompt:
Slow monotone drift never trips the monitor.

solve(states, k, m, tol, blowup): states [[x,v],...] of a spring integrator; E=0.5 m v^2+0.5 k x^2. Relative drift r=|E-E0|/E0 (absolute when E0=0). Scan in order: first state with E>blowup*E0 (E0>0) returns ["blowup", index, its r]. Otherwise ["drift", first index with r>tol, max r] or ["ok", -1, max r].

split: open-access


prompt:
Numerically dissipative integrators pass the monitor.

solve(states, k, m, tol, blowup): states [[x,v],...] of a spring integrator; E=0.5 m v^2+0.5 k x^2. Relative drift r=|E-E0|/E0 (absolute when E0=0). Scan in order: first state with E>blowup*E0 (E0>0) returns ["blowup", index, its r]. Otherwise ["drift", first index with r>tol, max r] or ["ok", -1, max r].

split: open-access


prompt:
A system starting at rest reports astronomically large drift for any motion.

solve(states, k, m, tol, blowup): states [[x,v],...] of a spring integrator; E=0.5 m v^2+0.5 k x^2. Relative drift r=|E-E0|/E0 (absolute when E0=0). Scan in order: first state with E>blowup*E0 (E0>0) returns ["blowup", index, its r]. Otherwise ["drift", first index with r>tol, max r] or ["ok", -1, max r].

split: open-access


prompt:
An exploding simulation is reported as mild drift.

solve(states, k, m, tol, blowup): states [[x,v],...] of a spring integrator; E=0.5 m v^2+0.5 k x^2. Relative drift r=|E-E0|/E0 (absolute when E0=0). Scan in order: first state with E>blowup*E0 (E0>0) returns ["blowup", index, its r]. Otherwise ["drift", first index with r>tol, max r] or ["ok", -1, max r].

split: open-access


prompt:
Explosions are detected one multiple of E0 too late.

solve(states, k, m, tol, blowup): states [[x,v],...] of a spring integrator; E=0.5 m v^2+0.5 k x^2. Relative drift r=|E-E0|/E0 (absolute when E0=0). Scan in order: first state with E>blowup*E0 (E0>0) returns ["blowup", index, its r]. Otherwise ["drift", first index with r>tol, max r] or ["ok", -1, max r].

split: open-access


prompt:
Diagnostics point at the end of the run instead of where drift began.

solve(states, k, m, tol, blowup): states [[x,v],...] of a spring integrator; E=0.5 m v^2+0.5 k x^2. Relative drift r=|E-E0|/E0 (absolute when E0=0). Scan in order: first state with E>blowup*E0 (E0>0) returns ["blowup", index, its r]. Otherwise ["drift", first index with r>tol, max r] or ["ok", -1, max r].

split: open-access


prompt:
Boxes whose x extents only touch never become a pair.

solve(boxes): boxes [id,minx,miny,maxx,maxy] with closed intervals (touching overlaps). Sweep x endpoints sorted by (coord, begin-before-end); on each begin, test y against every active box. Return sorted [min id, max id] pairs overlapping on both axes.

split: open-access


prompt:
Stacked boxes resting exactly on each other lose their pair.

solve(boxes): boxes [id,minx,miny,maxx,maxy] with closed intervals (touching overlaps). Sweep x endpoints sorted by (coord, begin-before-end); on each begin, test y against every active box. Return sorted [min id, max id] pairs overlapping on both axes.

split: open-access


prompt:
The pair cache sees (b,a) one frame and (a,b) the next, restarting contacts.

solve(boxes): boxes [id,minx,miny,maxx,maxy] with closed intervals (touching overlaps). Sweep x endpoints sorted by (coord, begin-before-end); on each begin, test y against every active box. Return sorted [min id, max id] pairs overlapping on both axes.

split: open-access


prompt:
Boxes far apart on x are reported as candidates.

solve(boxes): boxes [id,minx,miny,maxx,maxy] with closed intervals (touching overlaps). Sweep x endpoints sorted by (coord, begin-before-end); on each begin, test y against every active box. Return sorted [min id, max id] pairs overlapping on both axes.

split: open-access


prompt:
Tall thin boxes miss pairs and wide flat boxes gain false ones.

solve(boxes): boxes [id,minx,miny,maxx,maxy] with closed intervals (touching overlaps). Sweep x endpoints sorted by (coord, begin-before-end); on each begin, test y against every active box. Return sorted [min id, max id] pairs overlapping on both axes.

split: open-access


prompt:
Boxes straddling the origin share cell 0 with boxes one cell away.

solve(boxes, cs): insert each box [id,minx,miny,maxx,maxy] into every grid cell floor(min/cs)..floor(max/cs) inclusive on both axes. Return [sorted unique canonical candidate pairs sharing a cell, total cell insertions, largest bucket size].

split: open-access


prompt:
Boxes are missing from their last row and column of cells and contacts there are lost.

solve(boxes, cs): insert each box [id,minx,miny,maxx,maxy] into every grid cell floor(min/cs)..floor(max/cs) inclusive on both axes. Return [sorted unique canonical candidate pairs sharing a cell, total cell insertions, largest bucket size].

split: open-access


prompt:
Narrowphase runs the same pair once per shared cell.

solve(boxes, cs): insert each box [id,minx,miny,maxx,maxy] into every grid cell floor(min/cs)..floor(max/cs) inclusive on both axes. Return [sorted unique canonical candidate pairs sharing a cell, total cell insertions, largest bucket size].

split: open-access


prompt:
Tall boxes are inserted into too few rows, wide boxes into too many.

solve(boxes, cs): insert each box [id,minx,miny,maxx,maxy] into every grid cell floor(min/cs)..floor(max/cs) inclusive on both axes. Return [sorted unique canonical candidate pairs sharing a cell, total cell insertions, largest bucket size].

split: open-access


prompt:
Grid tuning picks cell sizes from a meaningless load metric.

solve(boxes, cs): insert each box [id,minx,miny,maxx,maxy] into every grid cell floor(min/cs)..floor(max/cs) inclusive on both axes. Return [sorted unique canonical candidate pairs sharing a cell, total cell insertions, largest bucket size].

split: open-access


prompt:
A proxy whose tight box touches its fat bound is reinserted every frame.

solve(tight, fat, disp, margin, mult): dynamic-tree proxy update. If the stored fat box contains the new tight box (inclusive) and its area is at most 4x that of a freshly built fat box, keep it: [False, fat]. Otherwise rebuild: tight expanded by margin on all sides, then extended by mult*disp on the side the motion points to; return [True, rebuilt box rounded to 6].

split: open-access


prompt:
Proxies moving left escape their fat box immediately and churn the tree.

solve(tight, fat, disp, margin, mult): dynamic-tree proxy update. If the stored fat box contains the new tight box (inclusive) and its area is at most 4x that of a freshly built fat box, keep it: [False, fat]. Otherwise rebuild: tight expanded by margin on all sides, then extended by mult*disp on the side the motion points to; return [True, rebuilt box rounded to 6].

split: open-access


prompt:
Jitter toward negative axes forces constant reinsertions.

solve(tight, fat, disp, margin, mult): dynamic-tree proxy update. If the stored fat box contains the new tight box (inclusive) and its area is at most 4x that of a freshly built fat box, keep it: [False, fat]. Otherwise rebuild: tight expanded by margin on all sides, then extended by mult*disp on the side the motion points to; return [True, rebuilt box rounded to 6].

split: open-access


prompt:
Falling bodies escape their fat boxes while sideways movers are fine.

solve(tight, fat, disp, margin, mult): dynamic-tree proxy update. If the stored fat box contains the new tight box (inclusive) and its area is at most 4x that of a freshly built fat box, keep it: [False, fat]. Otherwise rebuild: tight expanded by margin on all sides, then extended by mult*disp on the side the motion points to; return [True, rebuilt box rounded to 6].

split: open-access


prompt:
After a fast move stops, the huge fat box keeps generating false pairs.

solve(tight, fat, disp, margin, mult): dynamic-tree proxy update. If the stored fat box contains the new tight box (inclusive) and its area is at most 4x that of a freshly built fat box, keep it: [False, fat]. Otherwise rebuild: tight expanded by margin on all sides, then extended by mult*disp on the side the motion points to; return [True, rebuilt box rounded to 6].

split: open-access


prompt:
The shrink rule triggers at the wrong sizes.

solve(tight, fat, disp, margin, mult): dynamic-tree proxy update. If the stored fat box contains the new tight box (inclusive) and its area is at most 4x that of a freshly built fat box, keep it: [False, fat]. Otherwise rebuild: tight expanded by margin on all sides, then extended by mult*disp on the side the motion points to; return [True, rebuilt box rounded to 6].

split: open-access


prompt:
Bodies moving diagonally extend the wrong vertical side.

solve(tight, fat, disp, margin, mult): dynamic-tree proxy update. If the stored fat box contains the new tight box (inclusive) and its area is at most 4x that of a freshly built fat box, keep it: [False, fat]. Otherwise rebuild: tight expanded by margin on all sides, then extended by mult*disp on the side the motion points to; return [True, rebuilt box rounded to 6].

split: open-access


prompt:
Long thin scenes are cut across their narrow side and both children overlap heavily.

solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].

split: open-access


prompt:
Large primitives are placed on the wrong side of the split.

solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].

split: open-access


prompt:
Unbalanced splits are costed backwards.

solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].

split: open-access


prompt:
Tiny nodes are split although a leaf is cheaper, deepening the tree.

solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].

split: open-access


prompt:
Splitting off a single outlier on the far side is never considered.

solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].

split: open-access


prompt:
Split costs are halved relative to the leaf cost so splitting wins too often.

solve(prims): top-down BVH build step. Split axis = larger centroid extent (x on ties). Primitives sorted by centroid on that axis (index tiebreak). Cost of split k = 1 + (P(L)*k + P(R)*(n-k))/P(parent) with P the box perimeter of the primitives' bounds; leaf cost n. Return [best k or 0 for leaf, axis, cost rounded to 6, sorted left indices].

split: open-access


prompt:
Queries flush against an object edge return nothing.

solve(nodes, q): BVH nodes [minx,miny,maxx,maxy,left,right,leaf_id], leaves have left=-1; root is node 0. Stack traversal tests every popped node against the closed query box (counting each test) and descends only into overlapping internal nodes. Return [sorted leaf ids overlapping q, number of node tests].

split: open-access


prompt:
Every leaf under an overlapping parent is returned as a hit.

solve(nodes, q): BVH nodes [minx,miny,maxx,maxy,left,right,leaf_id], leaves have left=-1; root is node 0. Stack traversal tests every popped node against the closed query box (counting each test) and descends only into overlapping internal nodes. Return [sorted leaf ids overlapping q, number of node tests].

split: open-access


prompt:
Callers look up the wrong objects for every hit.

solve(nodes, q): BVH nodes [minx,miny,maxx,maxy,left,right,leaf_id], leaves have left=-1; root is node 0. Stack traversal tests every popped node against the closed query box (counting each test) and descends only into overlapping internal nodes. Return [sorted leaf ids overlapping q, number of node tests].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        cx = 1 if o[1] >= mx else 0
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[8, 6, 11, 9, 13], [47, 5, 10, 5, 12], [10, 7, 0, 7, 2], [32, 7, 6, 8, 8], [45, 13, 0, 13, 3], [14, 8, 2, 9, 3]], 2, 1, [3, 5, 4, 5]], [[8, 10, 32], 5, 1]], [[[[2, 13, 0, 16, 1], [21, 1, 6, 1, 6], [5, 5, 8, 8, 8], [39, 10, 6, 11, 9]], 2, 2, [14, 1, 19, 6]], [[2, 5, 39], 5, 1]], [[[[29, 1, 10, 1, 12], [19, 5, 10, 6, 11]], 2, 3, [3, 1, 8, 2]], [[19, 29], 1, 0]], [[[[41, 13, 0, 13, 2], [46, 3, 11, 3, 14], [28, 12, 0, 14, 3], [35, 14, 12, 16, 14], [27, 10, 15, 10, 15], [33, 0, 15, 0, 16]], 2, 3, [12, 14, 16, 16]], [[27, 35], 5, 1]], [[[[31, 11, 9, 12, 9], [29, 6, 3, 7, 5], [11, 14, 7, 14, 7], [16, 0, 7, 0, 9], [33, 15, 11, 16, 11], [4, 12, 0, 13, 3], [20, 12, 14, 13, 16], [49, 7, 6, 8, 7]], 1, 3, [12, 4, 14, 6]], [[4, 11, 16, 49], 13, 2]], [[[[43, 0, 6, 3, 7], [10, 9, 12, 9, 12], [14, 14, 11, 16, 13], [6, 9, 12, 11, 13], [27, 0, 5, 2, 7], [7, 5, 2, 8, 3], [23, 8, 2, 9, 4]], 1, 2, [9, 6, 12, 7]], [[7, 23], 13, 2]], [[[[40, 11, 13, 13, 16], [21, 2, 2, 5, 2], [46, 1, 11, 2, 13], [26, 11, 8, 14, 8], [28, 1, 3, 1, 3], [18, 6, 9, 6, 11], [17, 0, 1, 3, 2]], 3, 1, [9, 9, 12, 13]], [[26, 40], 5, 1]], [[[[8, 4, 3, 5, 5], [30, 7, 3, 8, 5], [26, 10, 12, 13, 14], [37, 7, 5, 10, 8], [47, 1, 9, 4, 10], [42, 5, 8, 5, 9], [36, 15, 14, 16, 16]], 1, 2, [8, 5, 13, 7]], [[8, 30, 37], 13, 2]]], [[[[[9, 5, 5, 7, 5], [31, 6, 15, 6, 15], [41, 14, 11, 14, 12], [19, 9, 4, 11, 6], [30, 14, 13, 16, 15], [39, 7, 5, 10, 7], [37, 0, 1, 2, 2], [3, 8, 9, 8, 10], [20, 6, 15, 6, 16]], 3, 1, [5, 9, 7, 9]], [[20, 31, 39], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[28, 15, 3, 16, 3], [15, 5, 14, 8, 15], [41, 10, 1, 11, 1], [45, 3, 11, 3, 14], [36, 5, 15, 8, 16], [47, 11, 5, 11, 8], [10, 6, 10, 9, 12], [11, 13, 12, 13, 14], [44, 8, 9, 10, 9]], 2, 3, [8, 12, 9, 13]], [[10, 11, 15, 36, 44, 45, 47], 5, 1]], [[[[24, 5, 10, 5, 11], [3, 13, 1, 16, 3], [22, 6, 7, 9, 8]], 3, 3, [10, 6, 15, 9]], [[3, 22, 24], 1, 0]], [[[[23, 10, 9, 10, 9], [14, 9, 3, 11, 3], [32, 14, 5, 16, 5], [40, 3, 2, 4, 4], [9, 5, 3, 8, 4]], 1, 1, [4, 3, 9, 4]], [[9, 14, 32, 40], 5, 1]], [[[[46, 11, 12, 13, 13], [4, 4, 11, 4, 14], [41, 4, 13, 4, 13], [2, 0, 8, 1, 11], [45, 5, 5, 8, 5], [3, 2, 4, 4, 5], [39, 15, 12, 16, 13], [25, 12, 8, 14, 11]], 1, 2, [0, 0, 5, 1]], [[3, 45], 13, 2]], [[[[23, 0, 12, 3, 13], [25, 7, 0, 9, 0], [18, 8, 9, 9, 9], [37, 3, 7, 5, 9], [21, 15, 5, 15, 5], [17, 11, 12, 12, 14], [3, 9, 10, 12, 11], [29, 0, 5, 0, 8], [40, 2, 4, 2, 7]], 1, 1, [12, 14, 12, 17]], [[3, 17, 18, 25, 29, 37], 5, 1]], [[[[31, 2, 8, 2, 11], [49, 7, 12, 7, 15], [38, 6, 6, 8, 7], [3, 8, 14, 8, 14], [48, 8, 9, 11, 11]], 3, 1, [9, 10, 9, 14]], [[3, 38, 48], 5, 1]]], [[[[[27, 14, 9, 16, 12], [35, 3, 9, 5, 11], [46, 6, 2, 6, 4], [32, 9, 6, 10, 8], [23, 4, 12, 5, 13]], 1, 2, [8, 13, 13, 15]], [[23, 27, 32, 35], 9, 2]], [[[[24, 6, 6, 9, 6], [27, 0, 1, 1, 3], [19, 4, 1, 4, 1]], 2, 2, [7, 8, 7, 10]], [[19, 24, 27], 5, 1]], [[[[17, 1, 13, 1, 15], [4, 12, 5, 14, 8], [42, 0, 3, 1, 5], [1, 15, 3, 16, 3]], 2, 1, [13, 14, 18, 18]], [[4], 5, 1]], [[[[15, 10, 8, 13, 11], [12, 14, 4, 16, 5], [28, 15, 13, 16, 13], [5, 3, 1, 4, 4], [29, 3, 0, 6, 2], [14, 6, 11, 8, 11], [37, 3, 11, 4, 13], [26, 13, 11, 15, 13], [35, 13, 9, 16, 12], [9, 15, 9, 16, 12]], 1, 1, [9, 14, 14, 18]], [[9, 14, 15, 26, 28, 35], 5, 1]], [[[[25, 2, 2, 3, 2], [19, 13, 7, 14, 7], [28, 4, 8, 7, 11], [18, 11, 3, 11, 3]], 2, 1, [11, 12, 14, 17]], [[], 5, 1]], [[[[25, 6, 10, 7, 12], [11, 4, 14, 5, 15], [28, 13, 0, 16, 1], [47, 15, 0, 16, 0], [49, 7, 8, 7, 10], [19, 8, 1, 9, 3], [41, 6, 12, 8, 14], [8, 6, 2, 6, 4]], 2, 3, [11, 9, 11, 13]], [[41], 13, 2]], [[[[27, 0, 2, 3, 3], [21, 0, 12, 2, 14], [38, 0, 2, 2, 5], [2, 0, 5, 3, 5], [31, 10, 9, 10, 12], [20, 10, 2, 11, 5]], 2, 2, [2, 10, 6, 14]], [[21], 9, 2]], [[[[8, 15, 5, 16, 6], [23, 12, 4, 12, 5], [39, 8, 1, 8, 1], [41, 13, 11, 15, 14], [27, 12, 11, 12, 12]], 1, 2, [8, 3, 10, 8]], [[27, 39, 41], 13, 2]]], [[[[[34, 6, 9, 8, 12], [46, 8, 0, 9, 2], [4, 8, 14, 11, 15], [16, 13, 9, 16, 11]], 3, 3, [0, 0, 5, 5]], [[34], 5, 1]], [[[[6, 8, 7, 9, 8], [36, 9, 11, 12, 12], [34, 11, 4, 14, 4], [42, 13, 0, 15, 0], [14, 14, 1, 16, 3], [47, 12, 0, 13, 2], [12, 15, 12, 15, 12], [49, 6, 13, 6, 15], [28, 8, 15, 11, 16], [5, 3, 13, 6, 14]], 2, 3, [7, 0, 11, 2]], [[6, 34], 17, 3]], [[[[32, 9, 4, 12, 4], [8, 9, 7, 12, 8], [24, 11, 10, 13, 13], [26, 8, 14, 10, 16], [40, 12, 5, 14, 6], [34, 9, 3, 11, 4], [45, 10, 0, 12, 3]], 3, 1, [5, 11, 5, 13]], [[8], 5, 1]], [[[[21, 14, 12, 16, 15], [13, 14, 8, 14, 8]], 3, 1, [7, 4, 9, 8]], [[13, 21], 1, 0]], [[[[41, 6, 5, 8, 5], [26, 7, 5, 10, 6], [45, 5, 12, 5, 12], [1, 3, 10, 4, 13], [44, 7, 14, 9, 14]], 1, 1, [8, 9, 8, 14]], [[1, 26, 41, 44, 45], 5, 1]], [[[[38, 4, 13, 5, 13], [4, 11, 10, 12, 13], [11, 3, 8, 6, 10], [3, 4, 10, 4, 12]], 1, 3, [11, 5, 13, 5]], [[], 9, 2]], [[[[41, 6, 14, 8, 14], [46, 5, 5, 8, 8], [44, 1, 1, 2, 3], [18, 0, 8, 1, 11], [30, 4, 5, 7, 6]], 3, 1, [10, 11, 10, 11]], [[41, 46], 5, 1]], [[[[7, 13, 7, 14, 10], [49, 6, 5, 9, 6], [35, 8, 9, 10, 9]], 2, 3, [0, 10, 0, 13]], [[7, 49], 5, 1]]], [[[[[39, 1, 10, 2, 13], [45, 11, 10, 13, 11], [12, 7, 6, 7, 6], [33, 6, 15, 9, 16], [47, 1, 8, 4, 11]], 1, 1, [9, 8, 14, 8]], [[33, 45], 5, 1]], [[[[43, 14, 12, 14, 12], [2, 5, 9, 5, 10], [32, 3, 7, 6, 8], [49, 4, 0, 6, 1], [11, 2, 7, 2, 10]], 1, 1, [6, 14, 11, 19]], [[2, 11, 32, 43], 5, 1]], [[[[8, 0, 11, 1, 11], [4, 5, 0, 8, 3], [26, 13, 14, 13, 14], [32, 1, 6, 2, 8], [16, 15, 6, 16, 9], [27, 8, 0, 8, 1], [24, 8, 0, 9, 0], [47, 3, 6, 6, 8], [46, 11, 7, 12, 8], [21, 5, 4, 8, 6], [6, 11, 10, 12, 13], [49, 9, 13, 9, 16]], 1, 2, [0, 9, 0, 14]], [[4, 8, 16, 21, 32, 46, 47], 13, 2]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]], [[[[17, 13, 7, 13, 8], [34, 1, 4, 3, 5], [18, 0, 15, 2, 16], [28, 8, 6, 11, 8], [23, 1, 2, 3, 2], [1, 0, 0, 3, 0], [40, 1, 0, 3, 1], [22, 5, 9, 6, 12], [38, 11, 3, 11, 6], [6, 0, 5, 0, 8]], 1, 2, [13, 0, 14, 4]], [[6, 17, 28, 38], 13, 2]], [[[[41, 10, 13, 10, 13], [4, 5, 13, 5, 14], [36, 10, 15, 12, 16], [35, 5, 5, 7, 6], [47, 9, 4, 10, 5], [27, 10, 14, 13, 14], [13, 8, 8, 10, 10], [15, 6, 14, 8, 14], [11, 11, 3, 13, 4]], 2, 2, [7, 2, 7, 7]], [[15, 35], 9, 2]], [[[[4, 15, 8, 16, 9], [30, 1, 0, 2, 0], [35, 15, 6, 16, 9], [12, 10, 4, 13, 7], [1, 2, 14, 5, 15], [28, 5, 2, 5, 5], [20, 15, 1, 15, 4], [46, 9, 0, 12, 0], [19, 4, 5, 5, 5], [43, 0, 9, 2, 11], [38, 6, 1, 9, 3], [7, 15, 6, 16, 8]], 3, 2, [14, 9, 16, 11]], [[4, 7, 35, 38], 5, 1]], [[[[46, 8, 9, 8, 9], [32, 1, 4, 1, 6], [8, 4, 11, 5, 13], [41, 1, 15, 3, 16], [28, 4, 14, 4, 16], [22, 10, 8, 12, 9], [26, 4, 0, 5, 0], [49, 8, 15, 8, 16], [4, 14, 9, 15, 12]], 3, 2, [14, 1, 16, 1]], [[], 9, 2]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        cx = 1 if (o[1] + o[3]) / 2 >= mx else 0
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[8, 6, 11, 9, 13], [47, 5, 10, 5, 12], [10, 7, 0, 7, 2], [32, 7, 6, 8, 8], [45, 13, 0, 13, 3], [14, 8, 2, 9, 3]], 2, 1, [3, 5, 4, 5]], [[8, 10, 32], 5, 1]], [[[[2, 13, 0, 16, 1], [21, 1, 6, 1, 6], [5, 5, 8, 8, 8], [39, 10, 6, 11, 9]], 2, 2, [14, 1, 19, 6]], [[2, 5, 39], 5, 1]], [[[[29, 1, 10, 1, 12], [19, 5, 10, 6, 11]], 2, 3, [3, 1, 8, 2]], [[19, 29], 1, 0]], [[[[41, 13, 0, 13, 2], [46, 3, 11, 3, 14], [28, 12, 0, 14, 3], [35, 14, 12, 16, 14], [27, 10, 15, 10, 15], [33, 0, 15, 0, 16]], 2, 3, [12, 14, 16, 16]], [[27, 35], 5, 1]], [[[[31, 11, 9, 12, 9], [29, 6, 3, 7, 5], [11, 14, 7, 14, 7], [16, 0, 7, 0, 9], [33, 15, 11, 16, 11], [4, 12, 0, 13, 3], [20, 12, 14, 13, 16], [49, 7, 6, 8, 7]], 1, 3, [12, 4, 14, 6]], [[4, 11, 16, 49], 13, 2]], [[[[43, 0, 6, 3, 7], [10, 9, 12, 9, 12], [14, 14, 11, 16, 13], [6, 9, 12, 11, 13], [27, 0, 5, 2, 7], [7, 5, 2, 8, 3], [23, 8, 2, 9, 4]], 1, 2, [9, 6, 12, 7]], [[7, 23], 13, 2]], [[[[40, 11, 13, 13, 16], [21, 2, 2, 5, 2], [46, 1, 11, 2, 13], [26, 11, 8, 14, 8], [28, 1, 3, 1, 3], [18, 6, 9, 6, 11], [17, 0, 1, 3, 2]], 3, 1, [9, 9, 12, 13]], [[26, 40], 5, 1]], [[[[8, 4, 3, 5, 5], [30, 7, 3, 8, 5], [26, 10, 12, 13, 14], [37, 7, 5, 10, 8], [47, 1, 9, 4, 10], [42, 5, 8, 5, 9], [36, 15, 14, 16, 16]], 1, 2, [8, 5, 13, 7]], [[8, 30, 37], 13, 2]]], [[[[[9, 5, 5, 7, 5], [31, 6, 15, 6, 15], [41, 14, 11, 14, 12], [19, 9, 4, 11, 6], [30, 14, 13, 16, 15], [39, 7, 5, 10, 7], [37, 0, 1, 2, 2], [3, 8, 9, 8, 10], [20, 6, 15, 6, 16]], 3, 1, [5, 9, 7, 9]], [[20, 31, 39], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[28, 15, 3, 16, 3], [15, 5, 14, 8, 15], [41, 10, 1, 11, 1], [45, 3, 11, 3, 14], [36, 5, 15, 8, 16], [47, 11, 5, 11, 8], [10, 6, 10, 9, 12], [11, 13, 12, 13, 14], [44, 8, 9, 10, 9]], 2, 3, [8, 12, 9, 13]], [[10, 11, 15, 36, 44, 45, 47], 5, 1]], [[[[24, 5, 10, 5, 11], [3, 13, 1, 16, 3], [22, 6, 7, 9, 8]], 3, 3, [10, 6, 15, 9]], [[3, 22, 24], 1, 0]], [[[[23, 10, 9, 10, 9], [14, 9, 3, 11, 3], [32, 14, 5, 16, 5], [40, 3, 2, 4, 4], [9, 5, 3, 8, 4]], 1, 1, [4, 3, 9, 4]], [[9, 14, 32, 40], 5, 1]], [[[[46, 11, 12, 13, 13], [4, 4, 11, 4, 14], [41, 4, 13, 4, 13], [2, 0, 8, 1, 11], [45, 5, 5, 8, 5], [3, 2, 4, 4, 5], [39, 15, 12, 16, 13], [25, 12, 8, 14, 11]], 1, 2, [0, 0, 5, 1]], [[3, 45], 13, 2]], [[[[23, 0, 12, 3, 13], [25, 7, 0, 9, 0], [18, 8, 9, 9, 9], [37, 3, 7, 5, 9], [21, 15, 5, 15, 5], [17, 11, 12, 12, 14], [3, 9, 10, 12, 11], [29, 0, 5, 0, 8], [40, 2, 4, 2, 7]], 1, 1, [12, 14, 12, 17]], [[3, 17, 18, 25, 29, 37], 5, 1]], [[[[31, 2, 8, 2, 11], [49, 7, 12, 7, 15], [38, 6, 6, 8, 7], [3, 8, 14, 8, 14], [48, 8, 9, 11, 11]], 3, 1, [9, 10, 9, 14]], [[3, 38, 48], 5, 1]]], [[[[[27, 14, 9, 16, 12], [35, 3, 9, 5, 11], [46, 6, 2, 6, 4], [32, 9, 6, 10, 8], [23, 4, 12, 5, 13]], 1, 2, [8, 13, 13, 15]], [[23, 27, 32, 35], 9, 2]], [[[[24, 6, 6, 9, 6], [27, 0, 1, 1, 3], [19, 4, 1, 4, 1]], 2, 2, [7, 8, 7, 10]], [[19, 24, 27], 5, 1]], [[[[17, 1, 13, 1, 15], [4, 12, 5, 14, 8], [42, 0, 3, 1, 5], [1, 15, 3, 16, 3]], 2, 1, [13, 14, 18, 18]], [[4], 5, 1]], [[[[15, 10, 8, 13, 11], [12, 14, 4, 16, 5], [28, 15, 13, 16, 13], [5, 3, 1, 4, 4], [29, 3, 0, 6, 2], [14, 6, 11, 8, 11], [37, 3, 11, 4, 13], [26, 13, 11, 15, 13], [35, 13, 9, 16, 12], [9, 15, 9, 16, 12]], 1, 1, [9, 14, 14, 18]], [[9, 14, 15, 26, 28, 35], 5, 1]], [[[[25, 2, 2, 3, 2], [19, 13, 7, 14, 7], [28, 4, 8, 7, 11], [18, 11, 3, 11, 3]], 2, 1, [11, 12, 14, 17]], [[], 5, 1]], [[[[25, 6, 10, 7, 12], [11, 4, 14, 5, 15], [28, 13, 0, 16, 1], [47, 15, 0, 16, 0], [49, 7, 8, 7, 10], [19, 8, 1, 9, 3], [41, 6, 12, 8, 14], [8, 6, 2, 6, 4]], 2, 3, [11, 9, 11, 13]], [[41], 13, 2]], [[[[27, 0, 2, 3, 3], [21, 0, 12, 2, 14], [38, 0, 2, 2, 5], [2, 0, 5, 3, 5], [31, 10, 9, 10, 12], [20, 10, 2, 11, 5]], 2, 2, [2, 10, 6, 14]], [[21], 9, 2]], [[[[8, 15, 5, 16, 6], [23, 12, 4, 12, 5], [39, 8, 1, 8, 1], [41, 13, 11, 15, 14], [27, 12, 11, 12, 12]], 1, 2, [8, 3, 10, 8]], [[27, 39, 41], 13, 2]]], [[[[[34, 6, 9, 8, 12], [46, 8, 0, 9, 2], [4, 8, 14, 11, 15], [16, 13, 9, 16, 11]], 3, 3, [0, 0, 5, 5]], [[34], 5, 1]], [[[[6, 8, 7, 9, 8], [36, 9, 11, 12, 12], [34, 11, 4, 14, 4], [42, 13, 0, 15, 0], [14, 14, 1, 16, 3], [47, 12, 0, 13, 2], [12, 15, 12, 15, 12], [49, 6, 13, 6, 15], [28, 8, 15, 11, 16], [5, 3, 13, 6, 14]], 2, 3, [7, 0, 11, 2]], [[6, 34], 17, 3]], [[[[32, 9, 4, 12, 4], [8, 9, 7, 12, 8], [24, 11, 10, 13, 13], [26, 8, 14, 10, 16], [40, 12, 5, 14, 6], [34, 9, 3, 11, 4], [45, 10, 0, 12, 3]], 3, 1, [5, 11, 5, 13]], [[8], 5, 1]], [[[[21, 14, 12, 16, 15], [13, 14, 8, 14, 8]], 3, 1, [7, 4, 9, 8]], [[13, 21], 1, 0]], [[[[41, 6, 5, 8, 5], [26, 7, 5, 10, 6], [45, 5, 12, 5, 12], [1, 3, 10, 4, 13], [44, 7, 14, 9, 14]], 1, 1, [8, 9, 8, 14]], [[1, 26, 41, 44, 45], 5, 1]], [[[[38, 4, 13, 5, 13], [4, 11, 10, 12, 13], [11, 3, 8, 6, 10], [3, 4, 10, 4, 12]], 1, 3, [11, 5, 13, 5]], [[], 9, 2]], [[[[41, 6, 14, 8, 14], [46, 5, 5, 8, 8], [44, 1, 1, 2, 3], [18, 0, 8, 1, 11], [30, 4, 5, 7, 6]], 3, 1, [10, 11, 10, 11]], [[41, 46], 5, 1]], [[[[7, 13, 7, 14, 10], [49, 6, 5, 9, 6], [35, 8, 9, 10, 9]], 2, 3, [0, 10, 0, 13]], [[7, 49], 5, 1]]], [[[[[39, 1, 10, 2, 13], [45, 11, 10, 13, 11], [12, 7, 6, 7, 6], [33, 6, 15, 9, 16], [47, 1, 8, 4, 11]], 1, 1, [9, 8, 14, 8]], [[33, 45], 5, 1]], [[[[43, 14, 12, 14, 12], [2, 5, 9, 5, 10], [32, 3, 7, 6, 8], [49, 4, 0, 6, 1], [11, 2, 7, 2, 10]], 1, 1, [6, 14, 11, 19]], [[2, 11, 32, 43], 5, 1]], [[[[8, 0, 11, 1, 11], [4, 5, 0, 8, 3], [26, 13, 14, 13, 14], [32, 1, 6, 2, 8], [16, 15, 6, 16, 9], [27, 8, 0, 8, 1], [24, 8, 0, 9, 0], [47, 3, 6, 6, 8], [46, 11, 7, 12, 8], [21, 5, 4, 8, 6], [6, 11, 10, 12, 13], [49, 9, 13, 9, 16]], 1, 2, [0, 9, 0, 14]], [[4, 8, 16, 21, 32, 46, 47], 13, 2]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]], [[[[17, 13, 7, 13, 8], [34, 1, 4, 3, 5], [18, 0, 15, 2, 16], [28, 8, 6, 11, 8], [23, 1, 2, 3, 2], [1, 0, 0, 3, 0], [40, 1, 0, 3, 1], [22, 5, 9, 6, 12], [38, 11, 3, 11, 6], [6, 0, 5, 0, 8]], 1, 2, [13, 0, 14, 4]], [[6, 17, 28, 38], 13, 2]], [[[[41, 10, 13, 10, 13], [4, 5, 13, 5, 14], [36, 10, 15, 12, 16], [35, 5, 5, 7, 6], [47, 9, 4, 10, 5], [27, 10, 14, 13, 14], [13, 8, 8, 10, 10], [15, 6, 14, 8, 14], [11, 11, 3, 13, 4]], 2, 2, [7, 2, 7, 7]], [[15, 35], 9, 2]], [[[[4, 15, 8, 16, 9], [30, 1, 0, 2, 0], [35, 15, 6, 16, 9], [12, 10, 4, 13, 7], [1, 2, 14, 5, 15], [28, 5, 2, 5, 5], [20, 15, 1, 15, 4], [46, 9, 0, 12, 0], [19, 4, 5, 5, 5], [43, 0, 9, 2, 11], [38, 6, 1, 9, 3], [7, 15, 6, 16, 8]], 3, 2, [14, 9, 16, 11]], [[4, 7, 35, 38], 5, 1]], [[[[46, 8, 9, 8, 9], [32, 1, 4, 1, 6], [8, 4, 11, 5, 13], [41, 1, 15, 3, 16], [28, 4, 14, 4, 16], [22, 10, 8, 12, 9], [26, 4, 0, 5, 0], [49, 8, 15, 8, 16], [4, 14, 9, 15, 12]], 3, 2, [14, 1, 16, 1]], [[], 9, 2]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Queries on the right half miss objects that extend across the midline.

solve(objs, cap, max_depth, q): quadtree over [0,16]^2. Insert [id,minx,miny,maxx,maxy] in order. A node splits when it holds more than cap objects and depth<max_depth; children are ordered cy*2+cx. An object goes to a child only if it fits entirely: maxx<mid -> left, minx>=mid -> right (same for y); straddlers stay. On split all node objects are re-inserted. Query returns [sorted ids of objects in nodes whose closed bounds overlap q, total node count, max depth].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] > mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[8, 7, 2, 8, 5], [41, 12, 8, 14, 11], [5, 2, 6, 2, 9], [38, 10, 5, 12, 5], [9, 0, 3, 1, 5], [24, 4, 0, 6, 3]], 2, 3, [11, 10, 12, 12]], [[5, 8, 41], 5, 1]], [[[[49, 7, 3, 10, 3], [38, 8, 0, 8, 2], [11, 12, 4, 12, 4], [5, 4, 10, 4, 11], [3, 12, 6, 15, 7], [21, 0, 13, 1, 14], [35, 10, 7, 10, 10], [9, 9, 10, 12, 12]], 2, 2, [9, 2, 10, 7]], [[35, 38, 49], 9, 2]], [[[[2, 13, 0, 16, 1], [21, 1, 6, 1, 6], [5, 5, 8, 8, 8], [39, 10, 6, 11, 9]], 2, 2, [14, 1, 19, 6]], [[2, 5, 39], 5, 1]], [[[[28, 10, 6, 13, 7], [40, 6, 0, 9, 2], [9, 1, 14, 3, 16]], 3, 2, [13, 2, 13, 7]], [[9, 28, 40], 1, 0]], [[[[41, 8, 14, 11, 16], [7, 7, 6, 8, 8], [38, 10, 10, 10, 13], [17, 7, 9, 8, 11], [2, 6, 3, 9, 4], [6, 12, 10, 12, 10], [30, 9, 12, 10, 12]], 3, 3, [1, 4, 1, 6]], [[2, 7, 17], 9, 2]], [[[[3, 15, 7, 16, 7], [5, 1, 8, 3, 10], [28, 2, 13, 3, 14], [8, 13, 13, 14, 14], [16, 8, 14, 11, 16], [42, 11, 14, 14, 14], [17, 0, 15, 1, 15]], 1, 1, [3, 9, 5, 14]], [[5, 17, 28], 5, 1]], [[[[40, 9, 14, 12, 15], [14, 9, 1, 10, 2], [37, 8, 7, 10, 7], [45, 7, 10, 7, 13], [11, 4, 1, 6, 4], [18, 10, 14, 11, 16]], 2, 2, [11, 14, 14, 15]], [[18, 40], 5, 1]], [[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]]], [[[[[10, 3, 15, 4, 15], [48, 15, 10, 15, 12], [19, 15, 9, 15, 12], [6, 7, 11, 8, 13], [45, 5, 14, 5, 16], [30, 13, 9, 14, 11], [25, 14, 13, 14, 13], [34, 15, 1, 15, 1]], 2, 1, [13, 2, 16, 2]], [[6, 34], 5, 1]], [[[[27, 11, 13, 14, 16], [22, 12, 7, 15, 7]], 3, 1, [2, 4, 7, 5]], [[22, 27], 1, 0]], [[[[2, 13, 13, 14, 13], [39, 12, 5, 12, 7], [33, 14, 5, 15, 7]], 3, 1, [12, 1, 17, 4]], [[2, 33, 39], 1, 0]], [[[[14, 10, 6, 10, 6], [3, 8, 10, 9, 10], [42, 13, 1, 15, 1], [46, 12, 1, 13, 1], [40, 14, 11, 14, 11], [27, 7, 4, 10, 4], [19, 9, 12, 12, 13]], 3, 2, [3, 6, 4, 7]], [[27], 5, 1]], [[[[20, 2, 5, 2, 5], [1, 4, 5, 4, 6], [36, 1, 1, 1, 1], [15, 3, 12, 3, 13], [9, 4, 6, 6, 7], [33, 14, 11, 16, 14], [24, 0, 4, 3, 5], [34, 6, 0, 9, 0]], 1, 3, [4, 4, 5, 5]], [[1, 9, 20, 24, 34, 36], 17, 3]], [[[[1, 4, 0, 5, 3], [17, 10, 15, 12, 16]], 2, 2, [13, 9, 14, 14]], [[1, 17], 1, 0]], [[[[28, 9, 14, 12, 16], [29, 2, 3, 2, 6], [23, 8, 0, 8, 2], [17, 2, 9, 5, 11], [33, 15, 5, 16, 7], [46, 14, 15, 16, 16], [14, 13, 0, 16, 3]], 2, 2, [0, 14, 1, 18]], [[17], 9, 2]], [[[[45, 15, 11, 16, 11], [24, 11, 4, 12, 5], [3, 1, 6, 1, 9], [37, 12, 8, 15, 11], [44, 7, 10, 9, 11], [9, 13, 4, 16, 5], [27, 11, 11, 11, 14]], 1, 3, [7, 13, 9, 15]], [[3, 27, 44], 17, 3]]], [[[[[1, 6, 9, 9, 12], [46, 1, 14, 4, 15], [45, 4, 13, 4, 16], [40, 3, 7, 6, 8], [24, 8, 12, 8, 13], [21, 4, 15, 4, 16], [7, 9, 11, 11, 14], [34, 11, 7, 13, 10]], 2, 2, [1, 9, 4, 14]], [[1, 21, 34, 40, 45, 46], 9, 2]], [[[[27, 0, 2, 3, 3], [21, 0, 12, 2, 14], [38, 0, 2, 2, 5], [2, 0, 5, 3, 5], [31, 10, 9, 10, 12], [20, 10, 2, 11, 5]], 2, 2, [2, 10, 6, 14]], [[21], 9, 2]], [[[[25, 2, 2, 3, 2], [19, 13, 7, 14, 7], [28, 4, 8, 7, 11], [18, 11, 3, 11, 3]], 2, 1, [11, 12, 14, 17]], [[], 5, 1]], [[[[42, 9, 0, 12, 2], [33, 14, 15, 15, 15], [46, 5, 9, 7, 12], [36, 11, 0, 13, 2], [43, 10, 3, 13, 4], [41, 4, 1, 6, 3], [49, 12, 12, 12, 14], [1, 10, 2, 12, 3], [11, 9, 7, 11, 10], [4, 8, 2, 8, 2]], 2, 1, [13, 13, 15, 15]], [[11, 33, 49], 5, 1]], [[[[33, 4, 12, 4, 12], [26, 7, 15, 8, 15], [29, 8, 7, 10, 7], [4, 15, 0, 15, 3], [15, 7, 13, 7, 14], [16, 7, 6, 10, 9], [5, 8, 3, 8, 3], [31, 14, 15, 14, 16], [22, 3, 2, 5, 3]], 3, 1, [3, 7, 5, 11]], [[15, 16, 22, 26, 33], 5, 1]], [[[[30, 9, 5, 12, 7], [25, 13, 6, 13, 6], [20, 0, 3, 1, 5], [10, 11, 13, 11, 15], [33, 6, 3, 9, 6], [17, 9, 9, 10, 11], [45, 3, 9, 4, 11], [5, 10, 4, 11, 6], [43, 8, 9, 9, 12], [39, 7, 15, 10, 16]], 1, 1, [1, 10, 5, 11]], [[33, 39, 45], 5, 1]], [[[[46, 4, 0, 4, 0], [7, 14, 13, 16, 14], [25, 10, 11, 11, 14], [33, 14, 8, 16, 10], [9, 12, 5, 15, 8], [19, 2, 12, 3, 14], [42, 2, 13, 2, 13], [13, 15, 15, 16, 15], [34, 15, 7, 15, 10], [5, 8, 10, 9, 10]], 1, 3, [4, 3, 8, 7]], [[9, 34, 46], 21, 3]], [[[[7, 12, 2, 12, 5], [38, 9, 14, 9, 16], [5, 5, 12, 7, 13], [14, 11, 3, 11, 3], [26, 0, 4, 3, 5], [6, 12, 1, 12, 1], [27, 7, 3, 10, 5], [22, 14, 1, 15, 2]], 2, 2, [5, 10, 10, 13]], [[5, 27, 38], 9, 2]]], [[[[[28, 6, 13, 6, 15], [12, 0, 1, 0, 3], [30, 1, 2, 2, 2], [9, 14, 12, 16, 13], [7, 5, 11, 8, 12]], 1, 3, [8, 2, 12, 3]], [[7], 13, 3]], [[[[46, 13, 3, 16, 4], [35, 8, 3, 9, 3], [29, 9, 8, 12, 9], [9, 4, 15, 6, 16], [32, 2, 6, 3, 6], [23, 1, 1, 2, 3], [49, 9, 11, 10, 12], [27, 2, 5, 5, 8]], 1, 2, [0, 13, 4, 15]], [[9, 27], 17, 2]], [[[[13, 10, 13, 11, 13], [3, 2, 3, 3, 4], [39, 8, 13, 9, 13], [43, 1, 1, 2, 3], [31, 3, 13, 5, 14], [4, 15, 12, 16, 13], [17, 6, 8, 7, 8], [24, 3, 3, 6, 6], [15, 11, 6, 11, 6]], 3, 3, [14, 14, 17, 16]], [[4, 13, 39], 5, 1]], [[[[17, 6, 9, 8, 12], [37, 8, 2, 10, 2], [42, 11, 14, 12, 14], [39, 9, 8, 10, 9], [34, 7, 2, 7, 5], [32, 13, 4, 16, 7], [23, 2, 9, 2, 10], [1, 4, 10, 7, 13], [40, 4, 2, 4, 3], [29, 4, 11, 6, 14]], 2, 2, [0, 9, 3, 13]], [[1, 17, 23, 29], 9, 2]], [[[[17, 1, 10, 4, 12], [11, 9, 3, 9, 4], [36, 1, 13, 3, 15], [49, 3, 14, 5, 16], [7, 8, 0, 10, 0], [39, 1, 15, 2, 16], [23, 1, 12, 2, 15], [8, 6, 14, 8, 16], [43, 11, 13, 11, 16], [29, 11, 8, 12, 9], [32, 7, 5, 9, 8]], 3, 3, [3, 2, 3, 3]], [[8, 32], 9, 2]], [[[[7, 13, 7, 14, 10], [49, 6, 5, 9, 6], [35, 8, 9, 10, 9]], 2, 3, [0, 10, 0, 13]], [[7, 49], 5, 1]], [[[[12, 0, 8, 0, 10], [34, 13, 6, 15, 9], [33, 15, 14, 16, 16]], 2, 2, [12, 8, 16, 9]], [[33, 34], 5, 1]], [[[[12, 4, 4, 5, 4], [36, 13, 8, 13, 10], [9, 15, 1, 16, 2], [43, 9, 11, 12, 14], [17, 7, 15, 7, 15]], 1, 1, [11, 0, 13, 2]], [[9], 5, 1]]], [[[[[49, 11, 1, 11, 4], [4, 9, 14, 12, 16], [3, 1, 4, 2, 7], [11, 10, 4, 10, 5], [25, 6, 12, 9, 12], [26, 11, 14, 13, 15], [36, 3, 14, 6, 16], [18, 3, 1, 3, 2], [6, 15, 5, 16, 7], [31, 3, 11, 3, 12], [40, 2, 6, 4, 9]], 3, 3, [11, 14, 15, 14]], [[4, 25, 26, 40], 5, 1]], [[[[4, 15, 8, 16, 9], [30, 1, 0, 2, 0], [35, 15, 6, 16, 9], [12, 10, 4, 13, 7], [1, 2, 14, 5, 15], [28, 5, 2, 5, 5], [20, 15, 1, 15, 4], [46, 9, 0, 12, 0], [19, 4, 5, 5, 5], [43, 0, 9, 2, 11], [38, 6, 1, 9, 3], [7, 15, 6, 16, 8]], 3, 2, [14, 9, 16, 11]], [[4, 7, 35, 38], 5, 1]], [[[[29, 6, 0, 8, 3], [20, 11, 15, 11, 16], [27, 6, 12, 9, 15], [38, 0, 9, 2, 11], [30, 10, 9, 10, 10], [7, 2, 9, 3, 11], [48, 8, 11, 11, 14], [9, 2, 7, 2, 10]], 1, 2, [1, 4, 2, 6]], [[9, 27, 29], 13, 2]], [[[[27, 4, 14, 7, 14], [36, 6, 1, 8, 4], [10, 8, 9, 10, 11], [15, 13, 4, 13, 5], [24, 9, 5, 12, 7], [48, 11, 0, 14, 1], [20, 5, 6, 7, 9], [47, 1, 11, 1, 12]], 3, 3, [6, 7, 6, 7]], [[20, 36], 5, 1]], [[[[4, 7, 3, 10, 5], [26, 13, 7, 14, 7], [19, 14, 7, 14, 10], [23, 14, 7, 15, 10], [10, 7, 12, 10, 15], [11, 14, 7, 16, 8], [17, 8, 6, 8, 9], [13, 15, 9, 15, 11], [34, 5, 9, 8, 9], [9, 5, 7, 6, 10], [2, 7, 6, 8, 9], [14, 4, 8, 7, 8]], 2, 3, [3, 0, 3, 3]], [[2, 4, 9, 10, 11, 17, 19, 23, 34], 5, 1]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]], [[[[2, 6, 3, 8, 4], [12, 0, 8, 0, 8], [38, 9, 13, 11, 16], [4, 4, 1, 4, 3], [36, 14, 3, 15, 3], [48, 8, 14, 9, 16], [22, 4, 3, 5, 5], [3, 10, 9, 10, 12], [26, 6, 6, 7, 6], [11, 4, 15, 6, 16], [18, 9, 3, 12, 4], [27, 12, 1, 14, 2]], 1, 2, [1, 4, 2, 5]], [[2, 22], 21, 2]], [[[[41, 9, 3, 12, 4], [48, 3, 6, 4, 7], [28, 8, 15, 8, 15]], 3, 3, [10, 1, 13, 6]], [[28, 41, 48], 1, 0]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] <= mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[8, 7, 2, 8, 5], [41, 12, 8, 14, 11], [5, 2, 6, 2, 9], [38, 10, 5, 12, 5], [9, 0, 3, 1, 5], [24, 4, 0, 6, 3]], 2, 3, [11, 10, 12, 12]], [[5, 8, 41], 5, 1]], [[[[49, 7, 3, 10, 3], [38, 8, 0, 8, 2], [11, 12, 4, 12, 4], [5, 4, 10, 4, 11], [3, 12, 6, 15, 7], [21, 0, 13, 1, 14], [35, 10, 7, 10, 10], [9, 9, 10, 12, 12]], 2, 2, [9, 2, 10, 7]], [[35, 38, 49], 9, 2]], [[[[2, 13, 0, 16, 1], [21, 1, 6, 1, 6], [5, 5, 8, 8, 8], [39, 10, 6, 11, 9]], 2, 2, [14, 1, 19, 6]], [[2, 5, 39], 5, 1]], [[[[28, 10, 6, 13, 7], [40, 6, 0, 9, 2], [9, 1, 14, 3, 16]], 3, 2, [13, 2, 13, 7]], [[9, 28, 40], 1, 0]], [[[[41, 8, 14, 11, 16], [7, 7, 6, 8, 8], [38, 10, 10, 10, 13], [17, 7, 9, 8, 11], [2, 6, 3, 9, 4], [6, 12, 10, 12, 10], [30, 9, 12, 10, 12]], 3, 3, [1, 4, 1, 6]], [[2, 7, 17], 9, 2]], [[[[3, 15, 7, 16, 7], [5, 1, 8, 3, 10], [28, 2, 13, 3, 14], [8, 13, 13, 14, 14], [16, 8, 14, 11, 16], [42, 11, 14, 14, 14], [17, 0, 15, 1, 15]], 1, 1, [3, 9, 5, 14]], [[5, 17, 28], 5, 1]], [[[[40, 9, 14, 12, 15], [14, 9, 1, 10, 2], [37, 8, 7, 10, 7], [45, 7, 10, 7, 13], [11, 4, 1, 6, 4], [18, 10, 14, 11, 16]], 2, 2, [11, 14, 14, 15]], [[18, 40], 5, 1]], [[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]]], [[[[[10, 3, 15, 4, 15], [48, 15, 10, 15, 12], [19, 15, 9, 15, 12], [6, 7, 11, 8, 13], [45, 5, 14, 5, 16], [30, 13, 9, 14, 11], [25, 14, 13, 14, 13], [34, 15, 1, 15, 1]], 2, 1, [13, 2, 16, 2]], [[6, 34], 5, 1]], [[[[27, 11, 13, 14, 16], [22, 12, 7, 15, 7]], 3, 1, [2, 4, 7, 5]], [[22, 27], 1, 0]], [[[[2, 13, 13, 14, 13], [39, 12, 5, 12, 7], [33, 14, 5, 15, 7]], 3, 1, [12, 1, 17, 4]], [[2, 33, 39], 1, 0]], [[[[14, 10, 6, 10, 6], [3, 8, 10, 9, 10], [42, 13, 1, 15, 1], [46, 12, 1, 13, 1], [40, 14, 11, 14, 11], [27, 7, 4, 10, 4], [19, 9, 12, 12, 13]], 3, 2, [3, 6, 4, 7]], [[27], 5, 1]], [[[[20, 2, 5, 2, 5], [1, 4, 5, 4, 6], [36, 1, 1, 1, 1], [15, 3, 12, 3, 13], [9, 4, 6, 6, 7], [33, 14, 11, 16, 14], [24, 0, 4, 3, 5], [34, 6, 0, 9, 0]], 1, 3, [4, 4, 5, 5]], [[1, 9, 20, 24, 34, 36], 17, 3]], [[[[1, 4, 0, 5, 3], [17, 10, 15, 12, 16]], 2, 2, [13, 9, 14, 14]], [[1, 17], 1, 0]], [[[[28, 9, 14, 12, 16], [29, 2, 3, 2, 6], [23, 8, 0, 8, 2], [17, 2, 9, 5, 11], [33, 15, 5, 16, 7], [46, 14, 15, 16, 16], [14, 13, 0, 16, 3]], 2, 2, [0, 14, 1, 18]], [[17], 9, 2]], [[[[45, 15, 11, 16, 11], [24, 11, 4, 12, 5], [3, 1, 6, 1, 9], [37, 12, 8, 15, 11], [44, 7, 10, 9, 11], [9, 13, 4, 16, 5], [27, 11, 11, 11, 14]], 1, 3, [7, 13, 9, 15]], [[3, 27, 44], 17, 3]]], [[[[[1, 6, 9, 9, 12], [46, 1, 14, 4, 15], [45, 4, 13, 4, 16], [40, 3, 7, 6, 8], [24, 8, 12, 8, 13], [21, 4, 15, 4, 16], [7, 9, 11, 11, 14], [34, 11, 7, 13, 10]], 2, 2, [1, 9, 4, 14]], [[1, 21, 34, 40, 45, 46], 9, 2]], [[[[27, 0, 2, 3, 3], [21, 0, 12, 2, 14], [38, 0, 2, 2, 5], [2, 0, 5, 3, 5], [31, 10, 9, 10, 12], [20, 10, 2, 11, 5]], 2, 2, [2, 10, 6, 14]], [[21], 9, 2]], [[[[25, 2, 2, 3, 2], [19, 13, 7, 14, 7], [28, 4, 8, 7, 11], [18, 11, 3, 11, 3]], 2, 1, [11, 12, 14, 17]], [[], 5, 1]], [[[[42, 9, 0, 12, 2], [33, 14, 15, 15, 15], [46, 5, 9, 7, 12], [36, 11, 0, 13, 2], [43, 10, 3, 13, 4], [41, 4, 1, 6, 3], [49, 12, 12, 12, 14], [1, 10, 2, 12, 3], [11, 9, 7, 11, 10], [4, 8, 2, 8, 2]], 2, 1, [13, 13, 15, 15]], [[11, 33, 49], 5, 1]], [[[[33, 4, 12, 4, 12], [26, 7, 15, 8, 15], [29, 8, 7, 10, 7], [4, 15, 0, 15, 3], [15, 7, 13, 7, 14], [16, 7, 6, 10, 9], [5, 8, 3, 8, 3], [31, 14, 15, 14, 16], [22, 3, 2, 5, 3]], 3, 1, [3, 7, 5, 11]], [[15, 16, 22, 26, 33], 5, 1]], [[[[30, 9, 5, 12, 7], [25, 13, 6, 13, 6], [20, 0, 3, 1, 5], [10, 11, 13, 11, 15], [33, 6, 3, 9, 6], [17, 9, 9, 10, 11], [45, 3, 9, 4, 11], [5, 10, 4, 11, 6], [43, 8, 9, 9, 12], [39, 7, 15, 10, 16]], 1, 1, [1, 10, 5, 11]], [[33, 39, 45], 5, 1]], [[[[46, 4, 0, 4, 0], [7, 14, 13, 16, 14], [25, 10, 11, 11, 14], [33, 14, 8, 16, 10], [9, 12, 5, 15, 8], [19, 2, 12, 3, 14], [42, 2, 13, 2, 13], [13, 15, 15, 16, 15], [34, 15, 7, 15, 10], [5, 8, 10, 9, 10]], 1, 3, [4, 3, 8, 7]], [[9, 34, 46], 21, 3]], [[[[7, 12, 2, 12, 5], [38, 9, 14, 9, 16], [5, 5, 12, 7, 13], [14, 11, 3, 11, 3], [26, 0, 4, 3, 5], [6, 12, 1, 12, 1], [27, 7, 3, 10, 5], [22, 14, 1, 15, 2]], 2, 2, [5, 10, 10, 13]], [[5, 27, 38], 9, 2]]], [[[[[28, 6, 13, 6, 15], [12, 0, 1, 0, 3], [30, 1, 2, 2, 2], [9, 14, 12, 16, 13], [7, 5, 11, 8, 12]], 1, 3, [8, 2, 12, 3]], [[7], 13, 3]], [[[[46, 13, 3, 16, 4], [35, 8, 3, 9, 3], [29, 9, 8, 12, 9], [9, 4, 15, 6, 16], [32, 2, 6, 3, 6], [23, 1, 1, 2, 3], [49, 9, 11, 10, 12], [27, 2, 5, 5, 8]], 1, 2, [0, 13, 4, 15]], [[9, 27], 17, 2]], [[[[13, 10, 13, 11, 13], [3, 2, 3, 3, 4], [39, 8, 13, 9, 13], [43, 1, 1, 2, 3], [31, 3, 13, 5, 14], [4, 15, 12, 16, 13], [17, 6, 8, 7, 8], [24, 3, 3, 6, 6], [15, 11, 6, 11, 6]], 3, 3, [14, 14, 17, 16]], [[4, 13, 39], 5, 1]], [[[[17, 6, 9, 8, 12], [37, 8, 2, 10, 2], [42, 11, 14, 12, 14], [39, 9, 8, 10, 9], [34, 7, 2, 7, 5], [32, 13, 4, 16, 7], [23, 2, 9, 2, 10], [1, 4, 10, 7, 13], [40, 4, 2, 4, 3], [29, 4, 11, 6, 14]], 2, 2, [0, 9, 3, 13]], [[1, 17, 23, 29], 9, 2]], [[[[17, 1, 10, 4, 12], [11, 9, 3, 9, 4], [36, 1, 13, 3, 15], [49, 3, 14, 5, 16], [7, 8, 0, 10, 0], [39, 1, 15, 2, 16], [23, 1, 12, 2, 15], [8, 6, 14, 8, 16], [43, 11, 13, 11, 16], [29, 11, 8, 12, 9], [32, 7, 5, 9, 8]], 3, 3, [3, 2, 3, 3]], [[8, 32], 9, 2]], [[[[7, 13, 7, 14, 10], [49, 6, 5, 9, 6], [35, 8, 9, 10, 9]], 2, 3, [0, 10, 0, 13]], [[7, 49], 5, 1]], [[[[12, 0, 8, 0, 10], [34, 13, 6, 15, 9], [33, 15, 14, 16, 16]], 2, 2, [12, 8, 16, 9]], [[33, 34], 5, 1]], [[[[12, 4, 4, 5, 4], [36, 13, 8, 13, 10], [9, 15, 1, 16, 2], [43, 9, 11, 12, 14], [17, 7, 15, 7, 15]], 1, 1, [11, 0, 13, 2]], [[9], 5, 1]]], [[[[[49, 11, 1, 11, 4], [4, 9, 14, 12, 16], [3, 1, 4, 2, 7], [11, 10, 4, 10, 5], [25, 6, 12, 9, 12], [26, 11, 14, 13, 15], [36, 3, 14, 6, 16], [18, 3, 1, 3, 2], [6, 15, 5, 16, 7], [31, 3, 11, 3, 12], [40, 2, 6, 4, 9]], 3, 3, [11, 14, 15, 14]], [[4, 25, 26, 40], 5, 1]], [[[[4, 15, 8, 16, 9], [30, 1, 0, 2, 0], [35, 15, 6, 16, 9], [12, 10, 4, 13, 7], [1, 2, 14, 5, 15], [28, 5, 2, 5, 5], [20, 15, 1, 15, 4], [46, 9, 0, 12, 0], [19, 4, 5, 5, 5], [43, 0, 9, 2, 11], [38, 6, 1, 9, 3], [7, 15, 6, 16, 8]], 3, 2, [14, 9, 16, 11]], [[4, 7, 35, 38], 5, 1]], [[[[29, 6, 0, 8, 3], [20, 11, 15, 11, 16], [27, 6, 12, 9, 15], [38, 0, 9, 2, 11], [30, 10, 9, 10, 10], [7, 2, 9, 3, 11], [48, 8, 11, 11, 14], [9, 2, 7, 2, 10]], 1, 2, [1, 4, 2, 6]], [[9, 27, 29], 13, 2]], [[[[27, 4, 14, 7, 14], [36, 6, 1, 8, 4], [10, 8, 9, 10, 11], [15, 13, 4, 13, 5], [24, 9, 5, 12, 7], [48, 11, 0, 14, 1], [20, 5, 6, 7, 9], [47, 1, 11, 1, 12]], 3, 3, [6, 7, 6, 7]], [[20, 36], 5, 1]], [[[[4, 7, 3, 10, 5], [26, 13, 7, 14, 7], [19, 14, 7, 14, 10], [23, 14, 7, 15, 10], [10, 7, 12, 10, 15], [11, 14, 7, 16, 8], [17, 8, 6, 8, 9], [13, 15, 9, 15, 11], [34, 5, 9, 8, 9], [9, 5, 7, 6, 10], [2, 7, 6, 8, 9], [14, 4, 8, 7, 8]], 2, 3, [3, 0, 3, 3]], [[2, 4, 9, 10, 11, 17, 19, 23, 34], 5, 1]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]], [[[[2, 6, 3, 8, 4], [12, 0, 8, 0, 8], [38, 9, 13, 11, 16], [4, 4, 1, 4, 3], [36, 14, 3, 15, 3], [48, 8, 14, 9, 16], [22, 4, 3, 5, 5], [3, 10, 9, 10, 12], [26, 6, 6, 7, 6], [11, 4, 15, 6, 16], [18, 9, 3, 12, 4], [27, 12, 1, 14, 2]], 1, 2, [1, 4, 2, 5]], [[2, 22], 21, 2]], [[[[41, 9, 3, 12, 4], [48, 3, 6, 4, 7], [28, 8, 15, 8, 15]], 3, 3, [10, 1, 13, 6]], [[28, 41, 48], 1, 0]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Boundary-aligned objects pile up in parent nodes and inflate every query.

solve(objs, cap, max_depth, q): quadtree over [0,16]^2. Insert [id,minx,miny,maxx,maxy] in order. A node splits when it holds more than cap objects and depth<max_depth; children are ordered cy*2+cx. An object goes to a child only if it fits entirely: maxx<mid -> left, minx>=mid -> right (same for y); straddlers stay. On split all node objects are re-inserted. Query returns [sorted ids of objects in nodes whose closed bounds overlap q, total node count, max depth].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) >= cap and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[33, 5, 0, 5, 0], [11, 7, 11, 9, 13], [5, 15, 13, 16, 15], [6, 11, 8, 13, 11], [22, 14, 12, 16, 15], [34, 2, 8, 4, 8], [3, 2, 7, 3, 8], [31, 11, 2, 14, 5]], 1, 2, [8, 14, 9, 18]], [[3, 6, 11, 34], 9, 2]], [[[[14, 3, 6, 3, 7], [33, 13, 2, 16, 5], [4, 9, 15, 9, 15], [13, 7, 4, 9, 6], [45, 8, 14, 11, 16], [29, 11, 3, 11, 4], [43, 0, 2, 0, 5]], 1, 2, [12, 1, 17, 3]], [[13, 29, 33], 17, 2]], [[[[30, 11, 15, 14, 16], [41, 3, 15, 3, 16], [11, 3, 1, 3, 4], [17, 2, 13, 2, 14], [42, 14, 6, 16, 7], [2, 10, 9, 13, 9]], 2, 1, [7, 6, 9, 8]], [[2, 11, 17, 30, 41, 42], 5, 1]], [[[[7, 15, 7, 16, 9], [25, 3, 3, 6, 4], [9, 0, 4, 3, 6], [15, 11, 10, 14, 10]], 3, 2, [9, 10, 13, 13]], [[7, 15], 5, 1]], [[[[25, 10, 12, 13, 13], [34, 12, 13, 15, 15], [8, 9, 2, 10, 2]], 2, 2, [12, 11, 14, 13]], [[25, 34], 5, 1]], [[[[29, 1, 10, 1, 12], [19, 5, 10, 6, 11]], 2, 3, [3, 1, 8, 2]], [[19, 29], 1, 0]], [[[[31, 11, 9, 12, 9], [29, 6, 3, 7, 5], [11, 14, 7, 14, 7], [16, 0, 7, 0, 9], [33, 15, 11, 16, 11], [4, 12, 0, 13, 3], [20, 12, 14, 13, 16], [49, 7, 6, 8, 7]], 1, 3, [12, 4, 14, 6]], [[4, 11, 16, 49], 13, 2]], [[[[49, 7, 3, 10, 3], [38, 8, 0, 8, 2], [11, 12, 4, 12, 4], [5, 4, 10, 4, 11], [3, 12, 6, 15, 7], [21, 0, 13, 1, 14], [35, 10, 7, 10, 10], [9, 9, 10, 12, 12]], 2, 2, [9, 2, 10, 7]], [[35, 38, 49], 9, 2]]], [[[[[46, 11, 12, 13, 13], [4, 4, 11, 4, 14], [41, 4, 13, 4, 13], [2, 0, 8, 1, 11], [45, 5, 5, 8, 5], [3, 2, 4, 4, 5], [39, 15, 12, 16, 13], [25, 12, 8, 14, 11]], 1, 2, [0, 0, 5, 1]], [[3, 45], 13, 2]], [[[[28, 9, 14, 12, 16], [29, 2, 3, 2, 6], [23, 8, 0, 8, 2], [17, 2, 9, 5, 11], [33, 15, 5, 16, 7], [46, 14, 15, 16, 16], [14, 13, 0, 16, 3]], 2, 2, [0, 14, 1, 18]], [[17], 9, 2]], [[[[43, 15, 9, 16, 9], [33, 11, 1, 11, 2], [32, 13, 12, 14, 14], [49, 8, 4, 9, 4]], 1, 2, [4, 4, 5, 7]], [[], 13, 2]], [[[[49, 11, 0, 11, 3], [23, 7, 12, 8, 15], [14, 0, 5, 3, 6], [30, 1, 4, 3, 6], [37, 2, 5, 4, 6], [28, 9, 9, 11, 11]], 1, 3, [6, 1, 7, 3]], [[23, 37], 13, 3]], [[[[40, 2, 4, 4, 4], [39, 7, 9, 7, 12], [24, 5, 11, 5, 14], [34, 3, 14, 5, 16], [13, 2, 0, 3, 0], [37, 8, 1, 9, 4], [45, 10, 5, 13, 8], [27, 3, 14, 3, 16], [22, 14, 0, 14, 3]], 3, 2, [14, 3, 16, 4]], [[22, 37, 45], 9, 2]], [[[[28, 8, 5, 10, 8], [39, 4, 12, 4, 12], [10, 4, 1, 4, 4], [29, 14, 11, 16, 13], [4, 6, 14, 6, 14], [22, 1, 0, 3, 0]], 1, 1, [11, 11, 15, 15]], [[28, 29], 5, 1]], [[[[1, 4, 0, 5, 3], [17, 10, 15, 12, 16]], 2, 2, [13, 9, 14, 14]], [[1, 17], 1, 0]], [[[[10, 6, 9, 7, 12], [1, 4, 1, 6, 1], [47, 2, 4, 2, 4], [34, 5, 5, 6, 8], [37, 5, 5, 7, 5], [39, 5, 10, 5, 12], [42, 9, 1, 10, 2], [46, 0, 1, 2, 3], [16, 15, 9, 16, 10]], 1, 1, [3, 10, 3, 14]], [[10, 34, 39], 5, 1]]], [[[[[42, 9, 3, 10, 5], [26, 12, 6, 14, 7], [12, 15, 5, 16, 7], [28, 0, 7, 0, 8], [3, 1, 10, 3, 13], [22, 0, 11, 0, 14], [13, 5, 1, 8, 2], [45, 5, 7, 6, 10], [40, 13, 2, 14, 5]], 3, 3, [12, 11, 15, 11]], [[13, 28, 45], 9, 2]], [[[[25, 9, 7, 10, 8], [29, 11, 3, 11, 6], [9, 14, 6, 16, 7], [44, 4, 5, 4, 8], [35, 2, 15, 4, 15], [12, 9, 10, 10, 10], [10, 8, 7, 11, 8], [43, 15, 0, 16, 3], [22, 14, 0, 16, 0], [16, 15, 6, 16, 8]], 1, 3, [2, 8, 4, 13]], [[10, 16, 25, 35, 44], 13, 3]], [[[[18, 11, 11, 13, 11], [5, 13, 2, 16, 5], [20, 4, 15, 4, 15], [32, 7, 4, 10, 4]], 3, 2, [11, 3, 16, 7]], [[5, 32], 5, 1]], [[[[45, 6, 7, 8, 9], [29, 7, 0, 8, 1], [8, 2, 4, 3, 5], [39, 6, 9, 6, 10], [31, 7, 13, 7, 14], [47, 1, 2, 3, 4]], 3, 2, [1, 0, 1, 0]], [[8, 29, 45, 47], 5, 1]], [[[[35, 12, 4, 14, 4], [20, 10, 12, 10, 14], [9, 4, 13, 6, 13], [44, 12, 10, 14, 11], [12, 10, 6, 12, 8]], 1, 2, [5, 6, 7, 8]], [[9, 12], 9, 2]], [[[[45, 14, 6, 15, 9], [39, 2, 8, 3, 8], [34, 8, 1, 9, 1], [32, 14, 13, 16, 16], [46, 0, 14, 2, 14], [8, 4, 14, 7, 16], [16, 15, 13, 15, 14]], 2, 3, [5, 11, 8, 15]], [[8, 16, 32, 45], 9, 2]], [[[[31, 9, 1, 11, 1], [18, 6, 9, 9, 9], [28, 4, 7, 5, 8]], 2, 3, [14, 6, 16, 10]], [[18, 28, 31], 5, 1]], [[[[38, 4, 9, 7, 11], [44, 15, 10, 16, 12], [13, 13, 12, 13, 13]], 2, 3, [10, 5, 12, 6]], [[], 5, 1]]], [[[[[17, 6, 9, 8, 12], [37, 8, 2, 10, 2], [42, 11, 14, 12, 14], [39, 9, 8, 10, 9], [34, 7, 2, 7, 5], [32, 13, 4, 16, 7], [23, 2, 9, 2, 10], [1, 4, 10, 7, 13], [40, 4, 2, 4, 3], [29, 4, 11, 6, 14]], 2, 2, [0, 9, 3, 13]], [[1, 17, 23, 29], 9, 2]], [[[[34, 14, 5, 16, 8], [30, 14, 15, 16, 16], [19, 2, 8, 2, 10], [43, 14, 5, 16, 5], [47, 5, 8, 8, 8], [9, 8, 10, 8, 12], [8, 1, 14, 2, 16]], 3, 2, [4, 12, 4, 16]], [[8, 19, 34, 47], 5, 1]], [[[[42, 15, 0, 16, 0], [34, 2, 5, 2, 6], [30, 0, 9, 0, 11], [32, 12, 9, 13, 11], [24, 9, 2, 11, 2], [2, 7, 9, 7, 9], [20, 13, 13, 16, 14], [22, 3, 14, 5, 14]], 3, 2, [1, 11, 4, 15]], [[2, 22, 30], 5, 1]], [[[[3, 10, 6, 12, 7], [4, 10, 14, 11, 15], [29, 6, 7, 6, 10], [26, 10, 15, 11, 16]], 2, 3, [12, 12, 13, 13]], [[4, 26, 29], 5, 1]], [[[[12, 6, 1, 9, 3], [29, 14, 6, 16, 9]], 1, 2, [11, 9, 12, 9]], [[12, 29], 5, 1]], [[[[6, 4, 7, 6, 9], [39, 15, 0, 15, 2], [13, 11, 7, 12, 8], [7, 14, 1, 14, 1], [8, 14, 3, 14, 4], [5, 6, 13, 7, 15], [15, 1, 8, 2, 8]], 1, 3, [1, 7, 3, 10]], [[6, 13, 15], 17, 3]], [[[[41, 6, 5, 8, 5], [26, 7, 5, 10, 6], [45, 5, 12, 5, 12], [1, 3, 10, 4, 13], [44, 7, 14, 9, 14]], 1, 1, [8, 9, 8, 14]], [[1, 26, 41, 44, 45], 5, 1]], [[[[7, 13, 7, 14, 10], [49, 6, 5, 9, 6], [35, 8, 9, 10, 9]], 2, 3, [0, 10, 0, 13]], [[7, 49], 5, 1]]], [[[[[7, 10, 4, 10, 7], [28, 8, 10, 10, 13], [21, 14, 13, 16, 15], [9, 13, 6, 16, 7], [11, 11, 4, 11, 7], [27, 14, 5, 16, 8], [1, 0, 8, 3, 9], [19, 0, 7, 0, 8], [29, 0, 11, 1, 14]], 2, 2, [7, 6, 10, 6]], [[7, 11, 19, 27], 9, 2]], [[[[14, 6, 14, 7, 14], [42, 7, 2, 7, 5]], 1, 2, [5, 9, 7, 13]], [[14], 5, 1]], [[[[16, 13, 12, 14, 13], [6, 9, 12, 9, 14], [4, 5, 11, 7, 11], [22, 12, 2, 14, 4], [38, 1, 9, 1, 9], [19, 7, 11, 10, 14]], 2, 2, [13, 4, 18, 9]], [[6, 16, 19, 22], 5, 1]], [[[[29, 6, 0, 8, 3], [20, 11, 15, 11, 16], [27, 6, 12, 9, 15], [38, 0, 9, 2, 11], [30, 10, 9, 10, 10], [7, 2, 9, 3, 11], [48, 8, 11, 11, 14], [9, 2, 7, 2, 10]], 1, 2, [1, 4, 2, 6]], [[9, 27, 29], 13, 2]], [[[[30, 3, 7, 4, 8], [17, 13, 13, 13, 16], [36, 12, 0, 15, 1], [22, 12, 10, 15, 11]], 2, 1, [7, 4, 10, 7]], [[30, 36], 5, 1]], [[[[12, 0, 0, 1, 1], [5, 3, 7, 4, 10], [3, 10, 14, 13, 15]], 1, 1, [11, 9, 15, 10]], [[3, 5], 5, 1]], [[[[22, 10, 13, 12, 14], [17, 15, 1, 16, 4], [5, 11, 3, 12, 3], [49, 12, 0, 15, 0], [31, 2, 6, 2, 7], [18, 2, 12, 2, 14], [34, 2, 15, 2, 16], [28, 13, 14, 15, 16], [39, 0, 5, 3, 7], [30, 12, 1, 15, 1], [40, 0, 3, 1, 4], [45, 3, 6, 3, 9]], 2, 1, [0, 6, 2, 11]], [[18, 31, 34, 39, 40, 45], 5, 1]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap + 1 and n['d'] < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[33, 5, 0, 5, 0], [11, 7, 11, 9, 13], [5, 15, 13, 16, 15], [6, 11, 8, 13, 11], [22, 14, 12, 16, 15], [34, 2, 8, 4, 8], [3, 2, 7, 3, 8], [31, 11, 2, 14, 5]], 1, 2, [8, 14, 9, 18]], [[3, 6, 11, 34], 9, 2]], [[[[14, 3, 6, 3, 7], [33, 13, 2, 16, 5], [4, 9, 15, 9, 15], [13, 7, 4, 9, 6], [45, 8, 14, 11, 16], [29, 11, 3, 11, 4], [43, 0, 2, 0, 5]], 1, 2, [12, 1, 17, 3]], [[13, 29, 33], 17, 2]], [[[[30, 11, 15, 14, 16], [41, 3, 15, 3, 16], [11, 3, 1, 3, 4], [17, 2, 13, 2, 14], [42, 14, 6, 16, 7], [2, 10, 9, 13, 9]], 2, 1, [7, 6, 9, 8]], [[2, 11, 17, 30, 41, 42], 5, 1]], [[[[7, 15, 7, 16, 9], [25, 3, 3, 6, 4], [9, 0, 4, 3, 6], [15, 11, 10, 14, 10]], 3, 2, [9, 10, 13, 13]], [[7, 15], 5, 1]], [[[[25, 10, 12, 13, 13], [34, 12, 13, 15, 15], [8, 9, 2, 10, 2]], 2, 2, [12, 11, 14, 13]], [[25, 34], 5, 1]], [[[[29, 1, 10, 1, 12], [19, 5, 10, 6, 11]], 2, 3, [3, 1, 8, 2]], [[19, 29], 1, 0]], [[[[31, 11, 9, 12, 9], [29, 6, 3, 7, 5], [11, 14, 7, 14, 7], [16, 0, 7, 0, 9], [33, 15, 11, 16, 11], [4, 12, 0, 13, 3], [20, 12, 14, 13, 16], [49, 7, 6, 8, 7]], 1, 3, [12, 4, 14, 6]], [[4, 11, 16, 49], 13, 2]], [[[[49, 7, 3, 10, 3], [38, 8, 0, 8, 2], [11, 12, 4, 12, 4], [5, 4, 10, 4, 11], [3, 12, 6, 15, 7], [21, 0, 13, 1, 14], [35, 10, 7, 10, 10], [9, 9, 10, 12, 12]], 2, 2, [9, 2, 10, 7]], [[35, 38, 49], 9, 2]]], [[[[[46, 11, 12, 13, 13], [4, 4, 11, 4, 14], [41, 4, 13, 4, 13], [2, 0, 8, 1, 11], [45, 5, 5, 8, 5], [3, 2, 4, 4, 5], [39, 15, 12, 16, 13], [25, 12, 8, 14, 11]], 1, 2, [0, 0, 5, 1]], [[3, 45], 13, 2]], [[[[28, 9, 14, 12, 16], [29, 2, 3, 2, 6], [23, 8, 0, 8, 2], [17, 2, 9, 5, 11], [33, 15, 5, 16, 7], [46, 14, 15, 16, 16], [14, 13, 0, 16, 3]], 2, 2, [0, 14, 1, 18]], [[17], 9, 2]], [[[[43, 15, 9, 16, 9], [33, 11, 1, 11, 2], [32, 13, 12, 14, 14], [49, 8, 4, 9, 4]], 1, 2, [4, 4, 5, 7]], [[], 13, 2]], [[[[49, 11, 0, 11, 3], [23, 7, 12, 8, 15], [14, 0, 5, 3, 6], [30, 1, 4, 3, 6], [37, 2, 5, 4, 6], [28, 9, 9, 11, 11]], 1, 3, [6, 1, 7, 3]], [[23, 37], 13, 3]], [[[[40, 2, 4, 4, 4], [39, 7, 9, 7, 12], [24, 5, 11, 5, 14], [34, 3, 14, 5, 16], [13, 2, 0, 3, 0], [37, 8, 1, 9, 4], [45, 10, 5, 13, 8], [27, 3, 14, 3, 16], [22, 14, 0, 14, 3]], 3, 2, [14, 3, 16, 4]], [[22, 37, 45], 9, 2]], [[[[28, 8, 5, 10, 8], [39, 4, 12, 4, 12], [10, 4, 1, 4, 4], [29, 14, 11, 16, 13], [4, 6, 14, 6, 14], [22, 1, 0, 3, 0]], 1, 1, [11, 11, 15, 15]], [[28, 29], 5, 1]], [[[[1, 4, 0, 5, 3], [17, 10, 15, 12, 16]], 2, 2, [13, 9, 14, 14]], [[1, 17], 1, 0]], [[[[10, 6, 9, 7, 12], [1, 4, 1, 6, 1], [47, 2, 4, 2, 4], [34, 5, 5, 6, 8], [37, 5, 5, 7, 5], [39, 5, 10, 5, 12], [42, 9, 1, 10, 2], [46, 0, 1, 2, 3], [16, 15, 9, 16, 10]], 1, 1, [3, 10, 3, 14]], [[10, 34, 39], 5, 1]]], [[[[[42, 9, 3, 10, 5], [26, 12, 6, 14, 7], [12, 15, 5, 16, 7], [28, 0, 7, 0, 8], [3, 1, 10, 3, 13], [22, 0, 11, 0, 14], [13, 5, 1, 8, 2], [45, 5, 7, 6, 10], [40, 13, 2, 14, 5]], 3, 3, [12, 11, 15, 11]], [[13, 28, 45], 9, 2]], [[[[25, 9, 7, 10, 8], [29, 11, 3, 11, 6], [9, 14, 6, 16, 7], [44, 4, 5, 4, 8], [35, 2, 15, 4, 15], [12, 9, 10, 10, 10], [10, 8, 7, 11, 8], [43, 15, 0, 16, 3], [22, 14, 0, 16, 0], [16, 15, 6, 16, 8]], 1, 3, [2, 8, 4, 13]], [[10, 16, 25, 35, 44], 13, 3]], [[[[18, 11, 11, 13, 11], [5, 13, 2, 16, 5], [20, 4, 15, 4, 15], [32, 7, 4, 10, 4]], 3, 2, [11, 3, 16, 7]], [[5, 32], 5, 1]], [[[[45, 6, 7, 8, 9], [29, 7, 0, 8, 1], [8, 2, 4, 3, 5], [39, 6, 9, 6, 10], [31, 7, 13, 7, 14], [47, 1, 2, 3, 4]], 3, 2, [1, 0, 1, 0]], [[8, 29, 45, 47], 5, 1]], [[[[35, 12, 4, 14, 4], [20, 10, 12, 10, 14], [9, 4, 13, 6, 13], [44, 12, 10, 14, 11], [12, 10, 6, 12, 8]], 1, 2, [5, 6, 7, 8]], [[9, 12], 9, 2]], [[[[45, 14, 6, 15, 9], [39, 2, 8, 3, 8], [34, 8, 1, 9, 1], [32, 14, 13, 16, 16], [46, 0, 14, 2, 14], [8, 4, 14, 7, 16], [16, 15, 13, 15, 14]], 2, 3, [5, 11, 8, 15]], [[8, 16, 32, 45], 9, 2]], [[[[31, 9, 1, 11, 1], [18, 6, 9, 9, 9], [28, 4, 7, 5, 8]], 2, 3, [14, 6, 16, 10]], [[18, 28, 31], 5, 1]], [[[[38, 4, 9, 7, 11], [44, 15, 10, 16, 12], [13, 13, 12, 13, 13]], 2, 3, [10, 5, 12, 6]], [[], 5, 1]]], [[[[[17, 6, 9, 8, 12], [37, 8, 2, 10, 2], [42, 11, 14, 12, 14], [39, 9, 8, 10, 9], [34, 7, 2, 7, 5], [32, 13, 4, 16, 7], [23, 2, 9, 2, 10], [1, 4, 10, 7, 13], [40, 4, 2, 4, 3], [29, 4, 11, 6, 14]], 2, 2, [0, 9, 3, 13]], [[1, 17, 23, 29], 9, 2]], [[[[34, 14, 5, 16, 8], [30, 14, 15, 16, 16], [19, 2, 8, 2, 10], [43, 14, 5, 16, 5], [47, 5, 8, 8, 8], [9, 8, 10, 8, 12], [8, 1, 14, 2, 16]], 3, 2, [4, 12, 4, 16]], [[8, 19, 34, 47], 5, 1]], [[[[42, 15, 0, 16, 0], [34, 2, 5, 2, 6], [30, 0, 9, 0, 11], [32, 12, 9, 13, 11], [24, 9, 2, 11, 2], [2, 7, 9, 7, 9], [20, 13, 13, 16, 14], [22, 3, 14, 5, 14]], 3, 2, [1, 11, 4, 15]], [[2, 22, 30], 5, 1]], [[[[3, 10, 6, 12, 7], [4, 10, 14, 11, 15], [29, 6, 7, 6, 10], [26, 10, 15, 11, 16]], 2, 3, [12, 12, 13, 13]], [[4, 26, 29], 5, 1]], [[[[12, 6, 1, 9, 3], [29, 14, 6, 16, 9]], 1, 2, [11, 9, 12, 9]], [[12, 29], 5, 1]], [[[[6, 4, 7, 6, 9], [39, 15, 0, 15, 2], [13, 11, 7, 12, 8], [7, 14, 1, 14, 1], [8, 14, 3, 14, 4], [5, 6, 13, 7, 15], [15, 1, 8, 2, 8]], 1, 3, [1, 7, 3, 10]], [[6, 13, 15], 17, 3]], [[[[41, 6, 5, 8, 5], [26, 7, 5, 10, 6], [45, 5, 12, 5, 12], [1, 3, 10, 4, 13], [44, 7, 14, 9, 14]], 1, 1, [8, 9, 8, 14]], [[1, 26, 41, 44, 45], 5, 1]], [[[[7, 13, 7, 14, 10], [49, 6, 5, 9, 6], [35, 8, 9, 10, 9]], 2, 3, [0, 10, 0, 13]], [[7, 49], 5, 1]]], [[[[[7, 10, 4, 10, 7], [28, 8, 10, 10, 13], [21, 14, 13, 16, 15], [9, 13, 6, 16, 7], [11, 11, 4, 11, 7], [27, 14, 5, 16, 8], [1, 0, 8, 3, 9], [19, 0, 7, 0, 8], [29, 0, 11, 1, 14]], 2, 2, [7, 6, 10, 6]], [[7, 11, 19, 27], 9, 2]], [[[[14, 6, 14, 7, 14], [42, 7, 2, 7, 5]], 1, 2, [5, 9, 7, 13]], [[14], 5, 1]], [[[[16, 13, 12, 14, 13], [6, 9, 12, 9, 14], [4, 5, 11, 7, 11], [22, 12, 2, 14, 4], [38, 1, 9, 1, 9], [19, 7, 11, 10, 14]], 2, 2, [13, 4, 18, 9]], [[6, 16, 19, 22], 5, 1]], [[[[29, 6, 0, 8, 3], [20, 11, 15, 11, 16], [27, 6, 12, 9, 15], [38, 0, 9, 2, 11], [30, 10, 9, 10, 10], [7, 2, 9, 3, 11], [48, 8, 11, 11, 14], [9, 2, 7, 2, 10]], 1, 2, [1, 4, 2, 6]], [[9, 27, 29], 13, 2]], [[[[30, 3, 7, 4, 8], [17, 13, 13, 13, 16], [36, 12, 0, 15, 1], [22, 12, 10, 15, 11]], 2, 1, [7, 4, 10, 7]], [[30, 36], 5, 1]], [[[[12, 0, 0, 1, 1], [5, 3, 7, 4, 10], [3, 10, 14, 13, 15]], 1, 1, [11, 9, 15, 10]], [[3, 5], 5, 1]], [[[[22, 10, 13, 12, 14], [17, 15, 1, 16, 4], [5, 11, 3, 12, 3], [49, 12, 0, 15, 0], [31, 2, 6, 2, 7], [18, 2, 12, 2, 14], [34, 2, 15, 2, 16], [28, 13, 14, 15, 16], [39, 0, 5, 3, 7], [30, 12, 1, 15, 1], [40, 0, 3, 1, 4], [45, 3, 6, 3, 9]], 2, 1, [0, 6, 2, 11]], [[18, 31, 34, 39, 40, 45], 5, 1]], [[[[34, 13, 8, 16, 9], [35, 0, 9, 2, 12], [8, 11, 12, 13, 13], [43, 12, 9, 15, 9], [42, 12, 3, 15, 5], [21, 13, 3, 13, 3], [27, 12, 0, 12, 3], [37, 6, 2, 8, 5], [25, 0, 9, 2, 12]], 2, 3, [10, 6, 10, 11]], [[8, 37, 42], 13, 2]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Nodes split one object early, creating extra nodes.

solve(objs, cap, max_depth, q): quadtree over [0,16]^2. Insert [id,minx,miny,maxx,maxy] in order. A node splits when it holds more than cap objects and depth<max_depth; children are ordered cy*2+cx. An object goes to a child only if it fits entirely: maxx<mid -> left, minx>=mid -> right (same for y); straddlers stay. On split all node objects are re-inserted. Query returns [sorted ids of objects in nodes whose closed bounds overlap q, total node count, max depth].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] <= max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]], [[[[17, 1, 8, 3, 8], [10, 5, 2, 6, 2], [49, 4, 10, 5, 12], [3, 14, 4, 14, 4], [4, 11, 7, 13, 8], [29, 10, 1, 13, 1]], 1, 1, [12, 11, 16, 16]], [[4], 5, 1]], [[[[14, 3, 6, 3, 7], [33, 13, 2, 16, 5], [4, 9, 15, 9, 15], [13, 7, 4, 9, 6], [45, 8, 14, 11, 16], [29, 11, 3, 11, 4], [43, 0, 2, 0, 5]], 1, 2, [12, 1, 17, 3]], [[13, 29, 33], 17, 2]], [[[[30, 13, 10, 14, 12], [22, 15, 13, 16, 13], [29, 6, 6, 8, 6], [35, 4, 3, 7, 4], [20, 6, 0, 6, 0]], 2, 1, [10, 1, 14, 3]], [[29], 5, 1]], [[[[21, 6, 5, 6, 7], [31, 7, 11, 7, 12], [17, 1, 8, 3, 9], [14, 10, 14, 12, 14], [33, 4, 15, 6, 16]], 1, 1, [12, 10, 12, 15]], [[14], 5, 1]], [[[[28, 12, 2, 15, 5], [6, 4, 1, 6, 4], [47, 4, 10, 6, 11], [49, 8, 9, 9, 10], [41, 12, 4, 14, 7]], 1, 3, [2, 10, 5, 10]], [[47], 9, 2]], [[[[32, 9, 1, 11, 3], [9, 7, 15, 7, 16], [44, 9, 8, 10, 8], [45, 9, 10, 12, 12], [21, 6, 0, 9, 1]], 2, 1, [3, 6, 3, 7]], [[21], 5, 1]], [[[[48, 14, 14, 16, 16], [19, 15, 3, 15, 4], [34, 0, 5, 2, 8], [13, 5, 1, 8, 1], [21, 1, 15, 3, 15], [36, 5, 6, 7, 8], [28, 15, 2, 16, 5], [41, 4, 7, 6, 10]], 2, 3, [8, 2, 13, 6]], [[13, 19, 28, 34, 36, 41], 5, 1]]], [[[[[48, 15, 14, 16, 14], [2, 2, 13, 4, 15], [30, 0, 0, 3, 0], [43, 5, 5, 8, 8], [24, 7, 13, 7, 14]], 1, 1, [5, 3, 7, 6]], [[30, 43], 5, 1]], [[[[30, 13, 11, 14, 11], [37, 9, 10, 12, 13], [17, 4, 10, 5, 13], [2, 8, 8, 8, 11], [27, 12, 0, 12, 0], [31, 2, 3, 3, 4]], 1, 2, [11, 4, 12, 6]], [[27], 9, 2]], [[[[28, 8, 6, 10, 6], [2, 15, 11, 16, 14], [46, 11, 3, 12, 6], [48, 6, 1, 9, 1], [42, 6, 5, 7, 6], [20, 6, 0, 6, 0], [7, 15, 4, 16, 5], [25, 4, 15, 4, 16]], 1, 1, [2, 5, 6, 7]], [[20, 42, 48], 5, 1]], [[[[28, 15, 10, 15, 13], [3, 14, 15, 16, 16], [23, 15, 9, 16, 10], [7, 13, 13, 13, 15], [16, 6, 8, 6, 9]], 2, 2, [3, 13, 3, 18]], [[16], 9, 2]], [[[[16, 3, 6, 3, 6], [36, 2, 1, 3, 3], [34, 11, 1, 14, 3], [2, 15, 9, 16, 10], [48, 5, 3, 8, 3], [41, 1, 7, 3, 8], [17, 7, 6, 7, 8]], 1, 1, [2, 10, 4, 10]], [[17, 41, 48], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[49, 11, 10, 11, 10], [12, 1, 6, 1, 8], [45, 15, 11, 16, 11], [8, 13, 12, 14, 14], [47, 10, 8, 10, 9]], 1, 1, [4, 10, 7, 10]], [[12], 5, 1]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]]], [[[[[38, 4, 9, 7, 11], [44, 15, 10, 16, 12], [13, 13, 12, 13, 13]], 2, 3, [10, 5, 12, 6]], [[], 5, 1]], [[[[23, 8, 12, 9, 13], [11, 5, 4, 8, 6], [13, 4, 4, 4, 4], [40, 4, 5, 6, 5], [28, 15, 10, 16, 10], [14, 5, 14, 7, 16]], 3, 2, [2, 1, 4, 1]], [[11, 13, 40], 5, 1]], [[[[48, 13, 12, 14, 14], [15, 12, 15, 12, 16], [38, 14, 3, 16, 4], [22, 3, 6, 5, 7], [6, 0, 0, 2, 0], [10, 5, 6, 8, 6], [47, 4, 7, 5, 10], [21, 2, 10, 5, 10], [45, 12, 2, 13, 2]], 1, 1, [11, 2, 15, 7]], [[10, 38, 45, 47], 5, 1]], [[[[30, 4, 13, 4, 14], [46, 0, 12, 2, 13], [14, 9, 15, 12, 16], [43, 11, 7, 14, 7], [12, 11, 3, 12, 6], [33, 9, 10, 12, 10], [48, 1, 11, 1, 13], [25, 11, 9, 13, 10], [49, 6, 6, 7, 7]], 2, 1, [14, 2, 19, 5]], [[12, 43], 5, 1]], [[[[46, 5, 8, 5, 9], [8, 1, 13, 2, 15], [38, 8, 6, 9, 8], [14, 1, 15, 3, 16], [36, 10, 8, 11, 9], [4, 12, 5, 12, 8], [48, 1, 10, 1, 11], [42, 10, 7, 12, 9], [26, 11, 14, 12, 16], [17, 10, 9, 10, 12]], 2, 1, [8, 9, 11, 13]], [[4, 8, 14, 17, 26, 36, 38, 42, 46, 48], 5, 1]], [[[[31, 9, 9, 10, 12], [13, 5, 15, 7, 16], [33, 0, 4, 3, 5]], 2, 1, [12, 12, 16, 15]], [[31], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[6, 7, 4, 7, 5], [25, 5, 5, 7, 6], [31, 14, 13, 14, 13], [13, 3, 13, 5, 16]], 2, 3, [14, 8, 19, 8]], [[31], 5, 1]]], [[[[[46, 13, 3, 16, 4], [35, 8, 3, 9, 3], [29, 9, 8, 12, 9], [9, 4, 15, 6, 16], [32, 2, 6, 3, 6], [23, 1, 1, 2, 3], [49, 9, 11, 10, 12], [27, 2, 5, 5, 8]], 1, 2, [0, 13, 4, 15]], [[9, 27], 17, 2]], [[[[12, 4, 4, 5, 4], [36, 13, 8, 13, 10], [9, 15, 1, 16, 2], [43, 9, 11, 12, 14], [17, 7, 15, 7, 15]], 1, 1, [11, 0, 13, 2]], [[9], 5, 1]], [[[[29, 0, 6, 1, 7], [13, 7, 1, 7, 2], [45, 2, 2, 3, 2], [34, 3, 1, 3, 4], [46, 1, 6, 2, 8], [22, 5, 2, 5, 4]], 2, 1, [9, 11, 11, 14]], [[46], 5, 1]], [[[[30, 0, 15, 3, 15], [22, 7, 2, 10, 5], [39, 0, 4, 0, 6], [20, 13, 7, 15, 7], [28, 5, 8, 7, 10], [2, 9, 0, 9, 0], [25, 15, 15, 16, 16], [42, 1, 10, 4, 11], [6, 8, 8, 8, 10], [9, 11, 12, 12, 13]], 1, 2, [11, 5, 11, 6]], [[22], 17, 2]], [[[[35, 2, 3, 3, 6], [39, 15, 10, 15, 11], [1, 13, 12, 14, 15], [45, 5, 9, 8, 12], [48, 8, 14, 8, 14], [38, 8, 2, 11, 2], [37, 2, 11, 2, 12], [7, 12, 14, 15, 15]], 1, 2, [3, 6, 7, 7]], [[35, 45], 9, 2]], [[[[17, 1, 10, 4, 12], [11, 9, 3, 9, 4], [36, 1, 13, 3, 15], [49, 3, 14, 5, 16], [7, 8, 0, 10, 0], [39, 1, 15, 2, 16], [23, 1, 12, 2, 15], [8, 6, 14, 8, 16], [43, 11, 13, 11, 16], [29, 11, 8, 12, 9], [32, 7, 5, 9, 8]], 3, 3, [3, 2, 3, 3]], [[8, 32], 9, 2]], [[[[3, 14, 5, 15, 7], [29, 15, 0, 16, 1], [25, 1, 10, 1, 12], [10, 6, 14, 6, 16], [27, 5, 6, 5, 9], [43, 0, 10, 3, 13], [33, 4, 9, 7, 9], [45, 9, 4, 11, 7], [18, 8, 14, 11, 15], [28, 11, 9, 12, 10]], 1, 1, [8, 9, 11, 10]], [[10, 18, 25, 27, 28, 33, 43], 5, 1]], [[[[33, 4, 7, 7, 9], [26, 8, 5, 11, 8], [49, 6, 11, 6, 12], [7, 2, 3, 3, 5]], 1, 1, [11, 12, 14, 13]], [[26, 33], 5, 1]]], [[[[[22, 7, 14, 9, 16], [33, 3, 15, 5, 16], [46, 7, 10, 7, 12], [43, 15, 13, 16, 15]], 2, 1, [2, 9, 3, 14]], [[22, 33, 46], 5, 1]], [[[[29, 8, 4, 11, 7], [45, 0, 12, 1, 15], [20, 14, 7, 16, 7], [39, 4, 12, 6, 14], [25, 9, 7, 10, 8], [12, 8, 8, 11, 9], [26, 11, 12, 13, 13], [1, 4, 15, 6, 16], [32, 7, 10, 10, 12], [11, 7, 4, 7, 4]], 3, 2, [8, 0, 13, 2]], [[11, 20, 25, 29, 32], 5, 1]], [[[[28, 10, 12, 10, 12], [22, 9, 7, 12, 7], [4, 14, 4, 14, 5], [2, 7, 14, 9, 15]], 1, 3, [12, 1, 13, 5]], [[2, 4, 22], 9, 2]], [[[[35, 5, 11, 7, 12], [47, 3, 4, 6, 4], [27, 15, 1, 16, 1], [43, 12, 11, 13, 14], [49, 3, 15, 3, 16], [38, 6, 8, 6, 9], [25, 5, 12, 6, 15], [5, 5, 2, 7, 3], [45, 13, 1, 13, 4], [23, 14, 1, 16, 3]], 2, 1, [2, 11, 4, 12]], [[25, 35, 38, 49], 5, 1]], [[[[37, 11, 9, 14, 12], [38, 3, 1, 4, 1], [14, 6, 7, 8, 7], [45, 8, 2, 11, 3], [12, 0, 4, 3, 4]], 1, 1, [7, 12, 9, 13]], [[14, 37], 5, 1]], [[[[8, 0, 11, 1, 11], [4, 5, 0, 8, 3], [26, 13, 14, 13, 14], [32, 1, 6, 2, 8], [16, 15, 6, 16, 9], [27, 8, 0, 8, 1], [24, 8, 0, 9, 0], [47, 3, 6, 6, 8], [46, 11, 7, 12, 8], [21, 5, 4, 8, 6], [6, 11, 10, 12, 13], [49, 9, 13, 9, 16]], 1, 2, [0, 9, 0, 14]], [[4, 8, 16, 21, 32, 46, 47], 13, 2]], [[[[46, 8, 9, 8, 9], [32, 1, 4, 1, 6], [8, 4, 11, 5, 13], [41, 1, 15, 3, 16], [28, 4, 14, 4, 16], [22, 10, 8, 12, 9], [26, 4, 0, 5, 0], [49, 8, 15, 8, 16], [4, 14, 9, 15, 12]], 3, 2, [14, 1, 16, 1]], [[], 9, 2]], [[[[30, 3, 7, 4, 8], [17, 13, 13, 13, 16], [36, 12, 0, 15, 1], [22, 12, 10, 15, 11]], 2, 1, [7, 4, 10, 7]], [[30, 36], 5, 1]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(objs, cap, max_depth, q):
    def make(x, y, s, d):
        return {'x': x, 'y': y, 's': s, 'd': d, 'objs': [], 'kids': None}
    def child_index(n, o):
        h = n['s'] / 2
        mx, my = n['x'] + h, n['y'] + h
        if o[3] < mx:
            cx = 0
        elif o[1] >= mx:
            cx = 1
        else:
            return -1
        if o[4] < my:
            cy = 0
        elif o[2] >= my:
            cy = 1
        else:
            return -1
        return cy * 2 + cx
    def split(n):
        h = n['s'] / 2
        n['kids'] = [make(n['x'] + (k % 2) * h, n['y'] + (k // 2) * h, h, n['d'] + 1) for k in range(4)]
        old, n['objs'] = n['objs'], []
        for o in old:
            insert(n, o)
    def insert(n, o):
        if n['kids'] is not None:
            k = child_index(n, o)
            if k >= 0:
                insert(n['kids'][k], o)
                return
        n['objs'].append(o)
        if n['kids'] is None and len(n['objs']) > cap and n['d'] + 1 < max_depth:
            split(n)
    root = make(0, 0, 16, 0)
    for o in objs:
        insert(root, o)
    found, count, deep = [], 0, 0
    stack = [root]
    while stack:
        n = stack.pop()
        count += 1
        deep = max(deep, n['d'])
        if n['kids']:
            stack.extend(n['kids'])
        if n['x'] <= q[2] and q[0] <= n['x'] + n['s'] and n['y'] <= q[3] and q[1] <= n['y'] + n['s']:
            found.extend(o[0] for o in n['objs'])
    return [sorted(found), count, deep]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[[[[[11, 13, 14, 15, 15], [7, 15, 15, 16, 16], [21, 2, 5, 2, 5], [5, 13, 14, 13, 15], [37, 14, 6, 15, 7]], 2, 2, [13, 10, 18, 12]], [[5, 7, 11], 9, 2]], [[[[17, 1, 8, 3, 8], [10, 5, 2, 6, 2], [49, 4, 10, 5, 12], [3, 14, 4, 14, 4], [4, 11, 7, 13, 8], [29, 10, 1, 13, 1]], 1, 1, [12, 11, 16, 16]], [[4], 5, 1]], [[[[14, 3, 6, 3, 7], [33, 13, 2, 16, 5], [4, 9, 15, 9, 15], [13, 7, 4, 9, 6], [45, 8, 14, 11, 16], [29, 11, 3, 11, 4], [43, 0, 2, 0, 5]], 1, 2, [12, 1, 17, 3]], [[13, 29, 33], 17, 2]], [[[[30, 13, 10, 14, 12], [22, 15, 13, 16, 13], [29, 6, 6, 8, 6], [35, 4, 3, 7, 4], [20, 6, 0, 6, 0]], 2, 1, [10, 1, 14, 3]], [[29], 5, 1]], [[[[21, 6, 5, 6, 7], [31, 7, 11, 7, 12], [17, 1, 8, 3, 9], [14, 10, 14, 12, 14], [33, 4, 15, 6, 16]], 1, 1, [12, 10, 12, 15]], [[14], 5, 1]], [[[[28, 12, 2, 15, 5], [6, 4, 1, 6, 4], [47, 4, 10, 6, 11], [49, 8, 9, 9, 10], [41, 12, 4, 14, 7]], 1, 3, [2, 10, 5, 10]], [[47], 9, 2]], [[[[32, 9, 1, 11, 3], [9, 7, 15, 7, 16], [44, 9, 8, 10, 8], [45, 9, 10, 12, 12], [21, 6, 0, 9, 1]], 2, 1, [3, 6, 3, 7]], [[21], 5, 1]], [[[[48, 14, 14, 16, 16], [19, 15, 3, 15, 4], [34, 0, 5, 2, 8], [13, 5, 1, 8, 1], [21, 1, 15, 3, 15], [36, 5, 6, 7, 8], [28, 15, 2, 16, 5], [41, 4, 7, 6, 10]], 2, 3, [8, 2, 13, 6]], [[13, 19, 28, 34, 36, 41], 5, 1]]], [[[[[48, 15, 14, 16, 14], [2, 2, 13, 4, 15], [30, 0, 0, 3, 0], [43, 5, 5, 8, 8], [24, 7, 13, 7, 14]], 1, 1, [5, 3, 7, 6]], [[30, 43], 5, 1]], [[[[30, 13, 11, 14, 11], [37, 9, 10, 12, 13], [17, 4, 10, 5, 13], [2, 8, 8, 8, 11], [27, 12, 0, 12, 0], [31, 2, 3, 3, 4]], 1, 2, [11, 4, 12, 6]], [[27], 9, 2]], [[[[28, 8, 6, 10, 6], [2, 15, 11, 16, 14], [46, 11, 3, 12, 6], [48, 6, 1, 9, 1], [42, 6, 5, 7, 6], [20, 6, 0, 6, 0], [7, 15, 4, 16, 5], [25, 4, 15, 4, 16]], 1, 1, [2, 5, 6, 7]], [[20, 42, 48], 5, 1]], [[[[28, 15, 10, 15, 13], [3, 14, 15, 16, 16], [23, 15, 9, 16, 10], [7, 13, 13, 13, 15], [16, 6, 8, 6, 9]], 2, 2, [3, 13, 3, 18]], [[16], 9, 2]], [[[[16, 3, 6, 3, 6], [36, 2, 1, 3, 3], [34, 11, 1, 14, 3], [2, 15, 9, 16, 10], [48, 5, 3, 8, 3], [41, 1, 7, 3, 8], [17, 7, 6, 7, 8]], 1, 1, [2, 10, 4, 10]], [[17, 41, 48], 5, 1]], [[[[20, 12, 5, 13, 6], [26, 14, 0, 16, 1], [6, 1, 2, 1, 5], [35, 9, 1, 12, 1], [23, 3, 15, 4, 16]], 3, 1, [5, 12, 6, 17]], [[23], 5, 1]], [[[[49, 11, 10, 11, 10], [12, 1, 6, 1, 8], [45, 15, 11, 16, 11], [8, 13, 12, 14, 14], [47, 10, 8, 10, 9]], 1, 1, [4, 10, 7, 10]], [[12], 5, 1]], [[[[35, 4, 1, 4, 1], [1, 4, 2, 7, 4], [5, 12, 6, 15, 7]], 2, 1, [9, 7, 11, 11]], [[5], 5, 1]]], [[[[[38, 4, 9, 7, 11], [44, 15, 10, 16, 12], [13, 13, 12, 13, 13]], 2, 3, [10, 5, 12, 6]], [[], 5, 1]], [[[[23, 8, 12, 9, 13], [11, 5, 4, 8, 6], [13, 4, 4, 4, 4], [40, 4, 5, 6, 5], [28, 15, 10, 16, 10], [14, 5, 14, 7, 16]], 3, 2, [2, 1, 4, 1]], [[11, 13, 40], 5, 1]], [[[[48, 13, 12, 14, 14], [15, 12, 15, 12, 16], [38, 14, 3, 16, 4], [22, 3, 6, 5, 7], [6, 0, 0, 2, 0], [10, 5, 6, 8, 6], [47, 4, 7, 5, 10], [21, 2, 10, 5, 10], [45, 12, 2, 13, 2]], 1, 1, [11, 2, 15, 7]], [[10, 38, 45, 47], 5, 1]], [[[[30, 4, 13, 4, 14], [46, 0, 12, 2, 13], [14, 9, 15, 12, 16], [43, 11, 7, 14, 7], [12, 11, 3, 12, 6], [33, 9, 10, 12, 10], [48, 1, 11, 1, 13], [25, 11, 9, 13, 10], [49, 6, 6, 7, 7]], 2, 1, [14, 2, 19, 5]], [[12, 43], 5, 1]], [[[[46, 5, 8, 5, 9], [8, 1, 13, 2, 15], [38, 8, 6, 9, 8], [14, 1, 15, 3, 16], [36, 10, 8, 11, 9], [4, 12, 5, 12, 8], [48, 1, 10, 1, 11], [42, 10, 7, 12, 9], [26, 11, 14, 12, 16], [17, 10, 9, 10, 12]], 2, 1, [8, 9, 11, 13]], [[4, 8, 14, 17, 26, 36, 38, 42, 46, 48], 5, 1]], [[[[31, 9, 9, 10, 12], [13, 5, 15, 7, 16], [33, 0, 4, 3, 5]], 2, 1, [12, 12, 16, 15]], [[31], 5, 1]], [[[[25, 1, 10, 3, 11], [47, 2, 11, 5, 11], [38, 14, 11, 16, 12], [43, 8, 5, 9, 5]], 3, 1, [5, 8, 10, 12]], [[25, 38, 43, 47], 5, 1]], [[[[6, 7, 4, 7, 5], [25, 5, 5, 7, 6], [31, 14, 13, 14, 13], [13, 3, 13, 5, 16]], 2, 3, [14, 8, 19, 8]], [[31], 5, 1]]], [[[[[46, 13, 3, 16, 4], [35, 8, 3, 9, 3], [29, 9, 8, 12, 9], [9, 4, 15, 6, 16], [32, 2, 6, 3, 6], [23, 1, 1, 2, 3], [49, 9, 11, 10, 12], [27, 2, 5, 5, 8]], 1, 2, [0, 13, 4, 15]], [[9, 27], 17, 2]], [[[[12, 4, 4, 5, 4], [36, 13, 8, 13, 10], [9, 15, 1, 16, 2], [43, 9, 11, 12, 14], [17, 7, 15, 7, 15]], 1, 1, [11, 0, 13, 2]], [[9], 5, 1]], [[[[29, 0, 6, 1, 7], [13, 7, 1, 7, 2], [45, 2, 2, 3, 2], [34, 3, 1, 3, 4], [46, 1, 6, 2, 8], [22, 5, 2, 5, 4]], 2, 1, [9, 11, 11, 14]], [[46], 5, 1]], [[[[30, 0, 15, 3, 15], [22, 7, 2, 10, 5], [39, 0, 4, 0, 6], [20, 13, 7, 15, 7], [28, 5, 8, 7, 10], [2, 9, 0, 9, 0], [25, 15, 15, 16, 16], [42, 1, 10, 4, 11], [6, 8, 8, 8, 10], [9, 11, 12, 12, 13]], 1, 2, [11, 5, 11, 6]], [[22], 17, 2]], [[[[35, 2, 3, 3, 6], [39, 15, 10, 15, 11], [1, 13, 12, 14, 15], [45, 5, 9, 8, 12], [48, 8, 14, 8, 14], [38, 8, 2, 11, 2], [37, 2, 11, 2, 12], [7, 12, 14, 15, 15]], 1, 2, [3, 6, 7, 7]], [[35, 45], 9, 2]], [[[[17, 1, 10, 4, 12], [11, 9, 3, 9, 4], [36, 1, 13, 3, 15], [49, 3, 14, 5, 16], [7, 8, 0, 10, 0], [39, 1, 15, 2, 16], [23, 1, 12, 2, 15], [8, 6, 14, 8, 16], [43, 11, 13, 11, 16], [29, 11, 8, 12, 9], [32, 7, 5, 9, 8]], 3, 3, [3, 2, 3, 3]], [[8, 32], 9, 2]], [[[[3, 14, 5, 15, 7], [29, 15, 0, 16, 1], [25, 1, 10, 1, 12], [10, 6, 14, 6, 16], [27, 5, 6, 5, 9], [43, 0, 10, 3, 13], [33, 4, 9, 7, 9], [45, 9, 4, 11, 7], [18, 8, 14, 11, 15], [28, 11, 9, 12, 10]], 1, 1, [8, 9, 11, 10]], [[10, 18, 25, 27, 28, 33, 43], 5, 1]], [[[[33, 4, 7, 7, 9], [26, 8, 5, 11, 8], [49, 6, 11, 6, 12], [7, 2, 3, 3, 5]], 1, 1, [11, 12, 14, 13]], [[26, 33], 5, 1]]], [[[[[22, 7, 14, 9, 16], [33, 3, 15, 5, 16], [46, 7, 10, 7, 12], [43, 15, 13, 16, 15]], 2, 1, [2, 9, 3, 14]], [[22, 33, 46], 5, 1]], [[[[29, 8, 4, 11, 7], [45, 0, 12, 1, 15], [20, 14, 7, 16, 7], [39, 4, 12, 6, 14], [25, 9, 7, 10, 8], [12, 8, 8, 11, 9], [26, 11, 12, 13, 13], [1, 4, 15, 6, 16], [32, 7, 10, 10, 12], [11, 7, 4, 7, 4]], 3, 2, [8, 0, 13, 2]], [[11, 20, 25, 29, 32], 5, 1]], [[[[28, 10, 12, 10, 12], [22, 9, 7, 12, 7], [4, 14, 4, 14, 5], [2, 7, 14, 9, 15]], 1, 3, [12, 1, 13, 5]], [[2, 4, 22], 9, 2]], [[[[35, 5, 11, 7, 12], [47, 3, 4, 6, 4], [27, 15, 1, 16, 1], [43, 12, 11, 13, 14], [49, 3, 15, 3, 16], [38, 6, 8, 6, 9], [25, 5, 12, 6, 15], [5, 5, 2, 7, 3], [45, 13, 1, 13, 4], [23, 14, 1, 16, 3]], 2, 1, [2, 11, 4, 12]], [[25, 35, 38, 49], 5, 1]], [[[[37, 11, 9, 14, 12], [38, 3, 1, 4, 1], [14, 6, 7, 8, 7], [45, 8, 2, 11, 3], [12, 0, 4, 3, 4]], 1, 1, [7, 12, 9, 13]], [[14, 37], 5, 1]], [[[[8, 0, 11, 1, 11], [4, 5, 0, 8, 3], [26, 13, 14, 13, 14], [32, 1, 6, 2, 8], [16, 15, 6, 16, 9], [27, 8, 0, 8, 1], [24, 8, 0, 9, 0], [47, 3, 6, 6, 8], [46, 11, 7, 12, 8], [21, 5, 4, 8, 6], [6, 11, 10, 12, 13], [49, 9, 13, 9, 16]], 1, 2, [0, 9, 0, 14]], [[4, 8, 16, 21, 32, 46, 47], 13, 2]], [[[[46, 8, 9, 8, 9], [32, 1, 4, 1, 6], [8, 4, 11, 5, 13], [41, 1, 15, 3, 16], [28, 4, 14, 4, 16], [22, 10, 8, 12, 9], [26, 4, 0, 5, 0], [49, 8, 15, 8, 16], [4, 14, 9, 15, 12]], 3, 2, [14, 1, 16, 1]], [[], 9, 2]], [[[[30, 3, 7, 4, 8], [17, 13, 13, 13, 16], [36, 12, 0, 15, 1], [22, 12, 10, 15, 11]], 2, 1, [7, 4, 10, 7]], [[30, 36], 5, 1]]]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("case %d" % i, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
Degenerate clusters create nodes deeper than configured.

solve(objs, cap, max_depth, q): quadtree over [0,16]^2. Insert [id,minx,miny,maxx,maxy] in order. A node splits when it holds more than cap objects and depth<max_depth; children are ordered cy*2+cx. An object goes to a child only if it fits entirely: maxx<mid -> left, minx>=mid -> right (same for y); straddlers stay. On split all node objects are re-inserted. Query returns [sorted ids of objects in nodes whose closed bounds overlap q, total node count, max depth].

split: open-access