數據生成器 (python)

import sys
import random

def select_interval(n, allow_empty = False, allow_full = True):

    def select():
        if allow_empty:
            return sorted(random.choices(range(n + 1), k = 2))
        else:
            return sorted(random.sample(range(n + 1), k = 2))

    l, r = select()
    while not allow_full and l == 0 and r == n:
        l, r = select()

    return l + 1, r - l

V = 10**3
V_RANGE = range(-V, V + 1)
ALL_OP = ["INSERT", "DELETE", "MAKE-SAME", "REVERSE", "GET-SUM", "MAX-SUM"]

def main():
    if len(sys.argv) != 4:
        print(f"Usage: {sys.argv[0]} <N> <M> <seed>", file=sys.stderr)
        sys.exit(1)
    random.seed(sys.argv[-1])

    N = int(sys.argv[1])
    M = int(sys.argv[2])

    n = random.randint(1, N)

    print(n, M)

    print(*random.choices(V_RANGE, k = n))

    for _ in range(M):
        op_cand = list(ALL_OP)
        if n == 1:
            op_cand.remove("DELETE")
        if n == N:
            op_cand.remove("INSERT")
        op = random.choice(op_cand)

        match op:
            case 'INSERT':
                posi = random.randint(0, n)
                tot = random.randint(1, N - n)
                print(op, posi, tot, *random.choices(V_RANGE, k = tot))
                n += tot
            case 'DELETE':
                posi, tot = select_interval(n, allow_full = False)
                print(op, posi, tot)
                n -= tot
            case 'MAKE-SAME':
                print(op, *select_interval(n), random.randint(-V, V))
            case 'REVERSE':
                print(op, *select_interval(n))
            case 'GET-SUM':
                print(op, *select_interval(n, allow_empty = True))
            case 'MAX-SUM':
                print(op)

if __name__ == "__main__":
    main()

用法 python gen.py n m seed，n 是最大序列長度，m 是操作次數，seed 是隨機種子。

從 BZOJ 的數據來看（和洛谷數據編號不同），只有 2.in 和 4.in 的 GET-SUM 操作存在 tot=0 的情況，因此上面數據生成器也只有 GET-SUM 的 tot 可能等於 0。