broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    res = x['reserved_high']
    win = None
    low = high = 0
    out = []
    for t, prio in x['requests']:
        w = t // 1000
        if w != win:
            win, low, high = w, 0, 0
        if prio != 'low':
            ok = low + high < cap
        else:
            ok = low < cap - res and low + high < cap
        if ok:
            if prio == 'high':
                high += 1
            else:
                low += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, [low, high]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [4, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [8, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [4, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [5, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1003, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'low'],
                 [1, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[23, 'low'],
                 [30, 'batch'],
                 [460, 'batch'],
                 [783, 'low'],
                 [807, 'high'],
                 [926, 'low'],
                 [1133, 'low'],
                 [1169, 'low'],
                 [1221, 'high'],
                 [1686, 'low'],
                 [1702, 'low'],
                 [1740, 'low'],
                 [2424, 'low'],
                 [2472, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow'],
    [1, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [5, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [9, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [5, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [6, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1004, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [2, 'low'],
                 [2, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[284, 'batch'],
                 [629, 'low'],
                 [787, 'low'],
                 [903, 'low'],
                 [1032, 'batch'],
                 [1118, 'high'],
                 [1495, 'low'],
                 [1855, 'low'],
                 [1876, 'low'],
                 [1919, 'batch'],
                 [2238, 'high'],
                 [2382, 'batch'],
                 [2390, 'high'],
                 [2492, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [6, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [10, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [6, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [7, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1005, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [3, 'low'],
                 [3, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[99, 'low'],
                 [696, 'low'],
                 [811, 'batch'],
                 [837, 'low'],
                 [912, 'batch'],
                 [1070, 'low'],
                 [1174, 'batch'],
                 [1400, 'batch'],
                 [1530, 'low'],
                 [1887, 'high'],
                 [1994, 'batch'],
                 [2235, 'low'],
                 [2286, 'low'],
                 [2369, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [7, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [11, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [7, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [8, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1006, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [4, 'low'],
                 [4, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[279, 'high'],
                 [550, 'high'],
                 [665, 'low'],
                 [940, 'low'],
                 [1010, 'batch'],
                 [1022, 'low'],
                 [1597, 'low'],
                 [1623, 'batch'],
                 [1749, 'low'],
                 [1850, 'low'],
                 [2025, 'high'],
                 [2095, 'high'],
                 [2322, 'low'],
                 [2325, 'low']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [2, 2]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [8, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [12, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [8, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [9, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1007, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [5, 'low'],
                 [5, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[249, 'low'],
                 [476, 'low'],
                 [620, 'high'],
                 [621, 'high'],
                 [646, 'batch'],
                 [704, 'low'],
                 [832, 'batch'],
                 [989, 'batch'],
                 [1004, 'batch'],
                 [1140, 'low'],
                 [1764, 'low'],
                 [2209, 'high'],
                 [2225, 'batch'],
                 [2378, 'batch']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]]]
for label, args, expected in cases[N - 1]:
    check(label, 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

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    res = x['reserved_high']
    win = None
    low = high = 0
    out = []
    for t, prio in x['requests']:
        w = t // 1000
        if w != win:
            win, low, high = w, 0, 0
        if prio in ('high', 'critical'):
            ok = low + high < cap
        else:
            ok = low < cap - res and low + high < cap
        if ok:
            if prio == 'high':
                high += 1
            else:
                low += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, [low, high]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [4, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [8, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [4, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [5, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1003, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'low'],
                 [1, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[23, 'low'],
                 [30, 'batch'],
                 [460, 'batch'],
                 [783, 'low'],
                 [807, 'high'],
                 [926, 'low'],
                 [1133, 'low'],
                 [1169, 'low'],
                 [1221, 'high'],
                 [1686, 'low'],
                 [1702, 'low'],
                 [1740, 'low'],
                 [2424, 'low'],
                 [2472, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow'],
    [1, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [5, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [9, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [5, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [6, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1004, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [2, 'low'],
                 [2, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[284, 'batch'],
                 [629, 'low'],
                 [787, 'low'],
                 [903, 'low'],
                 [1032, 'batch'],
                 [1118, 'high'],
                 [1495, 'low'],
                 [1855, 'low'],
                 [1876, 'low'],
                 [1919, 'batch'],
                 [2238, 'high'],
                 [2382, 'batch'],
                 [2390, 'high'],
                 [2492, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [6, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [10, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [6, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [7, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1005, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [3, 'low'],
                 [3, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[99, 'low'],
                 [696, 'low'],
                 [811, 'batch'],
                 [837, 'low'],
                 [912, 'batch'],
                 [1070, 'low'],
                 [1174, 'batch'],
                 [1400, 'batch'],
                 [1530, 'low'],
                 [1887, 'high'],
                 [1994, 'batch'],
                 [2235, 'low'],
                 [2286, 'low'],
                 [2369, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [7, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [11, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [7, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [8, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1006, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [4, 'low'],
                 [4, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[279, 'high'],
                 [550, 'high'],
                 [665, 'low'],
                 [940, 'low'],
                 [1010, 'batch'],
                 [1022, 'low'],
                 [1597, 'low'],
                 [1623, 'batch'],
                 [1749, 'low'],
                 [1850, 'low'],
                 [2025, 'high'],
                 [2095, 'high'],
                 [2322, 'low'],
                 [2325, 'low']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [2, 2]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [8, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [12, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [8, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [9, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1007, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [5, 'low'],
                 [5, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[249, 'low'],
                 [476, 'low'],
                 [620, 'high'],
                 [621, 'high'],
                 [646, 'batch'],
                 [704, 'low'],
                 [832, 'batch'],
                 [989, 'batch'],
                 [1004, 'batch'],
                 [1140, 'low'],
                 [1764, 'low'],
                 [2209, 'high'],
                 [2225, 'batch'],
                 [2378, 'batch']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]]]
for label, args, expected in cases[N - 1]:
    check(label, 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:
Batch jobs tagged with a new label bypass the reserve and consume capacity meant for critical traffic.

Input {capacity, reserved_high, requests [[t_ms, priority]]} with nondecreasing t, one-second epoch windows. Only the exact label "high" is high priority; every other label is low. A high request is admitted while total admitted < capacity. A low request is admitted only while admitted low < capacity - reserved_high and total < capacity. Both counters reset each window. Return [decisions, [low, high] of the final window].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    res = x['reserved_high']
    win = None
    low = high = 0
    out = []
    for t, prio in x['requests']:
        w = t // 100
        if w != win:
            win, low, high = w, 0, 0
        if prio == 'high':
            ok = low + high < cap
        else:
            ok = low < cap - res and low + high < cap
        if ok:
            if prio == 'high':
                high += 1
            else:
                low += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, [low, high]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [4, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [8, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [4, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [5, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1003, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'low'],
                 [1, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[23, 'low'],
                 [30, 'batch'],
                 [460, 'batch'],
                 [783, 'low'],
                 [807, 'high'],
                 [926, 'low'],
                 [1133, 'low'],
                 [1169, 'low'],
                 [1221, 'high'],
                 [1686, 'low'],
                 [1702, 'low'],
                 [1740, 'low'],
                 [2424, 'low'],
                 [2472, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow'],
    [1, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [5, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [9, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [5, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [6, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1004, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [2, 'low'],
                 [2, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[284, 'batch'],
                 [629, 'low'],
                 [787, 'low'],
                 [903, 'low'],
                 [1032, 'batch'],
                 [1118, 'high'],
                 [1495, 'low'],
                 [1855, 'low'],
                 [1876, 'low'],
                 [1919, 'batch'],
                 [2238, 'high'],
                 [2382, 'batch'],
                 [2390, 'high'],
                 [2492, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [6, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [10, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [6, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [7, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1005, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [3, 'low'],
                 [3, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[99, 'low'],
                 [696, 'low'],
                 [811, 'batch'],
                 [837, 'low'],
                 [912, 'batch'],
                 [1070, 'low'],
                 [1174, 'batch'],
                 [1400, 'batch'],
                 [1530, 'low'],
                 [1887, 'high'],
                 [1994, 'batch'],
                 [2235, 'low'],
                 [2286, 'low'],
                 [2369, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [7, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [11, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [7, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [8, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1006, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [4, 'low'],
                 [4, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[279, 'high'],
                 [550, 'high'],
                 [665, 'low'],
                 [940, 'low'],
                 [1010, 'batch'],
                 [1022, 'low'],
                 [1597, 'low'],
                 [1623, 'batch'],
                 [1749, 'low'],
                 [1850, 'low'],
                 [2025, 'high'],
                 [2095, 'high'],
                 [2322, 'low'],
                 [2325, 'low']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [2, 2]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [8, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [12, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [8, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [9, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1007, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [5, 'low'],
                 [5, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[249, 'low'],
                 [476, 'low'],
                 [620, 'high'],
                 [621, 'high'],
                 [646, 'batch'],
                 [704, 'low'],
                 [832, 'batch'],
                 [989, 'batch'],
                 [1004, 'batch'],
                 [1140, 'low'],
                 [1764, 'low'],
                 [2209, 'high'],
                 [2225, 'batch'],
                 [2378, 'batch']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]]]
for label, args, expected in cases[N - 1]:
    check(label, 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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    cap = x['capacity']
    res = x['reserved_high']
    win = None
    low = high = 0
    out = []
    for t, prio in x['requests']:
        w = round(t / 1000)
        if w != win:
            win, low, high = w, 0, 0
        if prio == 'high':
            ok = low + high < cap
        else:
            ok = low < cap - res and low + high < cap
        if ok:
            if prio == 'high':
                high += 1
            else:
                low += 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, [low, high]]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [4, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [8, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [4, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [5, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1003, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'low'],
                 [1, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[23, 'low'],
                 [30, 'batch'],
                 [460, 'batch'],
                 [783, 'low'],
                 [807, 'high'],
                 [926, 'low'],
                 [1133, 'low'],
                 [1169, 'low'],
                 [1221, 'high'],
                 [1686, 'low'],
                 [1702, 'low'],
                 [1740, 'low'],
                 [2424, 'low'],
                 [2472, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow'],
    [1, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [5, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [9, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [5, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [6, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1004, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [2, 'low'],
                 [2, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[284, 'batch'],
                 [629, 'low'],
                 [787, 'low'],
                 [903, 'low'],
                 [1032, 'batch'],
                 [1118, 'high'],
                 [1495, 'low'],
                 [1855, 'low'],
                 [1876, 'low'],
                 [1919, 'batch'],
                 [2238, 'high'],
                 [2382, 'batch'],
                 [2390, 'high'],
                 [2492, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [1, 3]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [6, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [10, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [6, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [7, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1005, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [3, 'low'],
                 [3, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[99, 'low'],
                 [696, 'low'],
                 [811, 'batch'],
                 [837, 'low'],
                 [912, 'batch'],
                 [1070, 'low'],
                 [1174, 'batch'],
                 [1400, 'batch'],
                 [1530, 'low'],
                 [1887, 'high'],
                 [1994, 'batch'],
                 [2235, 'low'],
                 [2286, 'low'],
                 [2369, 'high']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'deny',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [7, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [11, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [7, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [8, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1006, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [4, 'low'],
                 [4, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[279, 'high'],
                 [550, 'high'],
                 [665, 'low'],
                 [940, 'low'],
                 [1010, 'batch'],
                 [1022, 'low'],
                 [1597, 'low'],
                 [1623, 'batch'],
                 [1749, 'low'],
                 [1850, 'low'],
                 [2025, 'high'],
                 [2095, 'high'],
                 [2322, 'low'],
                 [2325, 'low']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'allow',
     'allow'],
    [2, 2]]]],
 [['low traffic cannot take reserve',
   {'capacity': 5,
    'requests': [[0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [0, 'low'],
                 [1, 'high'],
                 [2, 'high'],
                 [8, 'high'],
                 [4, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
  ['high traffic blocks low at capacity',
   {'capacity': 4,
    'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [12, 'low']],
    'reserved_high': 1},
   [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
  ['unknown priority is low',
   {'capacity': 3,
    'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [8, 'high'], [4, 'critical']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
  ['custom label cannot claim reserve',
   {'capacity': 4,
    'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [9, 'high']],
    'reserved_high': 2},
   [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
  ['window reset clears both',
   {'capacity': 2,
    'requests': [[0, 'high'],
                 [1, 'high'],
                 [999, 'low'],
                 [1000, 'high'],
                 [1001, 'low'],
                 [1007, 'high']],
    'reserved_high': 1},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
  ['mixed within reserve',
   {'capacity': 6,
    'requests': [[0, 'high'],
                 [0, 'low'],
                 [0, 'high'],
                 [0, 'low'],
                 [0, 'low'],
                 [5, 'low'],
                 [5, 'high']],
    'reserved_high': 3},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
  ['random mix',
   {'capacity': 4,
    'requests': [[249, 'low'],
                 [476, 'low'],
                 [620, 'high'],
                 [621, 'high'],
                 [646, 'batch'],
                 [704, 'low'],
                 [832, 'batch'],
                 [989, 'batch'],
                 [1004, 'batch'],
                 [1140, 'low'],
                 [1764, 'low'],
                 [2209, 'high'],
                 [2225, 'batch'],
                 [2378, 'batch']],
    'reserved_high': 2},
   [['allow',
     'allow',
     'allow',
     'allow',
     'deny',
     'deny',
     'deny',
     'deny',
     'allow',
     'allow',
     'deny',
     'allow',
     'allow',
     'allow'],
    [2, 1]]]]]
for label, args, expected in cases[N - 1]:
    check(label, 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:
Counters reset every tenth of a second, so the per-second capacity is admitted ten times over.

Input {capacity, reserved_high, requests [[t_ms, priority]]} with nondecreasing t, one-second epoch windows. Only the exact label "high" is high priority; every other label is low. A high request is admitted while total admitted < capacity. A low request is admitted only while admitted low < capacity - reserved_high and total < capacity. Both counters reset each window. Return [decisions, [low, high] of the final window].

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = L
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
for label, args, expected in cases[N - 1]:
    check(label, 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

N = 1
observations = []
def solve(x):
    Q = x['quota']
    W = x['window_s']
    L = x['chunk']
    win = None
    remaining = 0
    local = {}
    out = []
    for t, node, op in x['events']:
        w = t // W
        if w != win:
            win, remaining, local = w, Q, {}
        if op == 'return':
            remaining += local.pop(node, 0)
            out.append(remaining)
            continue
        if local.get(node, 0) == 0:
            grant = L if remaining >= L else 0
            remaining -= grant
            local[node] = grant
        if local[node] > 0:
            local[node] -= 1
            out.append('allow')
        else:
            out.append('deny')
    return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [3, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [14, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [2, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [5, 'a', 'req'],
               [6, 'b', 'req'],
               [10, 'a', 'return'],
               [14, 'a', 'return'],
               [20, 'b', 'req'],
               [23, 'b', 'req'],
               [24, 'b', 'req'],
               [24, 'b', 'return'],
               [25, 'a', 'req'],
               [25, 'b', 'req'],
               [31, 'b', 'return'],
               [38, 'a', 'req'],
               [38, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     3,
     3,
     'allow',
     'allow',
     'allow',
     2,
     'allow',
     'deny',
     8,
     'allow',
     'allow'],
    2,
    [['a', 2], ['b', 2]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [4, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [15, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [3, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[1, 'a', 'req'],
               [13, 'a', 'req'],
               [15, 'b', 'req'],
               [22, 'a', 'req'],
               [25, 'a', 'req'],
               [25, 'a', 'return'],
               [26, 'b', 'req'],
               [26, 'b', 'return'],
               [29, 'b', 'req'],
               [39, 'b', 'req'],
               [44, 'a', 'req'],
               [48, 'a', 'req'],
               [48, 'a', 'return'],
               [49, 'b', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow',
     2,
     'allow',
     'allow',
     'allow',
     'allow',
     3,
     'allow'],
    3,
    [['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [5, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [16, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [4, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[0, 'a', 'return'],
               [9, 'a', 'req'],
               [9, 'a', 'return'],
               [16, 'a', 'req'],
               [22, 'a', 'req'],
               [24, 'a', 'req'],
               [32, 'b', 'req'],
               [34, 'a', 'req'],
               [35, 'b', 'return'],
               [36, 'b', 'req'],
               [40, 'a', 'req'],
               [44, 'a', 'return'],
               [45, 'b', 'req'],
               [48, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     2,
     'allow',
     'allow'],
    0,
    [['a', 1], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [6, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [8, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [17, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [5, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[4, 'b', 'req'],
               [8, 'a', 'req'],
               [17, 'b', 'req'],
               [20, 'b', 'req'],
               [26, 'a', 'return'],
               [28, 'b', 'req'],
               [32, 'b', 'req'],
               [36, 'a', 'req'],
               [38, 'b', 'req'],
               [40, 'a', 'req'],
               [41, 'a', 'req'],
               [42, 'a', 'req'],
               [42, 'a', 'return'],
               [43, 'a', 'req']],
    'quota': 8,
    'window_s': 30},
   [['allow',
     'allow',
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     'allow',
     1,
     'allow'],
    0,
    [['a', 0], ['b', 1]]]]],
 [['partial last chunk',
   {'chunk': 3,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [1, 'b', 'req'],
               [7, 'c', 'req']],
    'quota': 7,
    'window_s': 60},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
    0,
    [['a', 2], ['b', 0], ['c', 0]]]],
  ['return credits leftover',
   {'chunk': 4,
    'events': [[0, 'a', 'req'],
               [1, 'a', 'return'],
               [2, 'b', 'req'],
               [3, 'b', 'req'],
               [9, 'c', 'req']],
    'quota': 6,
    'window_s': 60},
   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
  ['window rollover voids leases',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [3, 'b', 'req'],
               [11, 'a', 'req'],
               [12, 'a', 'req'],
               [18, 'a', 'req']],
    'quota': 4,
    'window_s': 10},
   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
  ['exhausted lease refetches',
   {'chunk': 2,
    'events': [[0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [0, 'a', 'req'],
               [6, 'a', 'return']],
    'quota': 10,
    'window_s': 100},
   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
  ['global exhaustion',
   {'chunk': 2,
    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
    'quota': 3,
    'window_s': 100},
   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
  ['random nodes',
   {'chunk': 3,
    'events': [[8, 'b', 'return'],
               [10, 'b', 'req'],
               [11, 'a', 'req'],
               [11, 'a', 'return'],
               [14, 'b', 'req'],
               [25, 'a', 'req'],
               [26, 'b', 'req'],
               [35, 'a', 'req'],
               [35, 'a', 'return'],
               [39, 'a', 'req'],
               [40, 'a', 'req'],
               [43, 'b', 'req'],
               [44, 'b', 'return'],
               [47, 'a', 'return']],
    'quota': 8,
    'window_s': 30},
   [[8,
     'allow',
     'allow',
     4,
     'allow',
     'allow',
     'allow',
     'allow',
     7,
     'allow',
     'allow',
     'allow',
     3,
     4],
    4,
    []]]]]
for label, args, expected in cases[N - 1]:
    check(label, 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:
The fleet collectively admits more than the global quota.

Input {quota, window_s, chunk, events [[t, node, "req"|"return"]]} with nondecreasing t. Each epoch window starts with the full global quota and voids all node leases. A node with an empty lease fetches min(chunk, remaining) from the coordinator; each request spends one leased unit or is denied when none is available. "return" credits the node's unused lease back and reports the new remaining. Return [results, remaining, sorted [node, lease]].

split: open-access