Constraints

• 0 <= len(rules) <= 2000
• All CIDR strings are valid IPv4 CIDRs of the form `a.b.c.d/x` with `0 <= x <= 32`
• Rules must be processed sequentially in the given order
• Your solution must correctly handle splitting the remaining region into multiple disjoint intervals after an `allow` rule

Examples

Solution

def solution(target, rules):
    MAX32 = 0xFFFFFFFF

    def ip_to_int(ip):
        a, b, c, d = map(int, ip.split('.'))
        return (a << 24) | (b << 16) | (c << 8) | d

    def parse_cidr(cidr):
        ip_str, prefix_str = cidr.split('/')
        prefix = int(prefix_str)
        ip = ip_to_int(ip_str)

        if prefix == 0:
            start = 0
            end = MAX32
        else:
            mask = (MAX32 << (32 - prefix)) & MAX32
            start = ip & mask
            end = start | (MAX32 ^ mask)

        return start, end

    t_start, t_end = parse_cidr(target)
    remaining = [(t_start, t_end)]

    for rule_type, cidr in rules:
        r_start, r_end = parse_cidr(cidr)

        if rule_type == 'deny':
            for a, b in remaining:
                if b < r_start:
                    continue
                if a > r_end:
                    break
                return False
        else:
            new_remaining = []
            for a, b in remaining:
                if b < r_start or a > r_end:
                    new_remaining.append((a, b))
                else:
                    if a < r_start:
                        new_remaining.append((a, r_start - 1))
                    if r_end < b:
                        new_remaining.append((r_end + 1, b))
            remaining = new_remaining
            if not remaining:
                return True

    return not remaining

Time complexity: O(r * k) where `r` is the number of rules and `k` is the number of remaining intervals at each step; worst-case O(r^2). Space complexity: O(r) worst-case for storing the disjoint remaining intervals.

Hints

1. Convert each CIDR into an inclusive integer interval `[start, end]` using 32-bit IPv4 arithmetic.
2. Maintain the uncanceled part of the target as a sorted list of disjoint intervals. An `allow` subtracts from these intervals, while a `deny` only needs to detect whether any interval overlaps.