cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unittests/ds/grid/grid_cls_test.py
- View this file on GitHub
- Last update: 2025-07-11 23:11:42+09:00
- Problem: https://judge.yosupo.jp/problem/aplusb
Depends on
- cp_library/bit/pack/packer_cls.py
- cp_library/ds/grid/grid_cls.py
- cp_library/ds/list/list_find_fn.py
- cp_library/ds/view/view_cls.py
- cp_library/io/fast_io_cls.py
- cp_library/io/parser_cls.py
- cp_library/io/read_fn.py
- cp_library/io/write_fn.py
- cp_library/test/unittest_helper.py
Code
# verification-helper: PROBLEM https://judge.yosupo.jp/problem/aplusb
import pytest
import random
class TestGrid:
"""
Tests for Grid class with bit-packed storage.
IMPORTANT: Grid uses Packer(W-1) for bit packing, which means:
- Packer(W-1) creates s = (W-1).bit_length()
- Each row has length 1 << s (next power of 2 >= W)
- Examples:
- W=3: Packer(2) → s=2 → row length = 4
- W=5: Packer(4) → s=3 → row length = 8
- W=8: Packer(7) → s=3 → row length = 8
- W=50: Packer(49) → s=6 → row length = 64
"""
def test_initialization_single_value(self):
"""Test initialization with a single value"""
grid = Grid(3, 4, 5)
assert grid.H == 3
assert grid.W == 4
assert len(grid) == 3
# All elements should be 5
for i in range(3):
for j in range(4):
assert grid(i, j) == 5
def test_initialization_flat_list(self):
"""Test initialization with a flat list"""
# List smaller than grid size
flat_list = [1, 2, 3, 4, 5, 6, 7, 8]
grid = Grid(2, 4, flat_list)
assert grid.H == 2
assert grid.W == 4
# Should map flat list to 2D grid row by row
expected = [
[1, 2, 3, 4],
[5, 6, 7, 8]
]
for i in range(2):
for j in range(4):
assert grid(i, j) == expected[i][j]
def test_initialization_2d_list(self):
"""Test initialization with a 2D list"""
grid_2d = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
grid = Grid(3, 3, grid_2d)
assert grid.H == 3
assert grid.W == 3
for i in range(3):
for j in range(3):
assert grid(i, j) == grid_2d[i][j]
def test_initialization_large_list(self):
"""Test initialization with a list larger than grid size"""
large_list = list(range(20))
grid = Grid(2, 3, large_list)
assert grid.H == 2
assert grid.W == 3
# Should use the list directly
for i in range(2):
for j in range(3):
# Direct access to packed array
expected_index = grid.pkr.enc(i, j)
assert grid(i, j) == large_list[expected_index]
def test_getitem_returns_view(self):
"""Test that __getitem__ returns a view of the row"""
grid_2d = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
grid = Grid(3, 4, grid_2d)
# Get row views
row0 = grid[0]
row1 = grid[1]
row2 = grid[2]
# Check row contents - Packer(4-1) has s=2, so row length is 1<<2=4
assert len(row0) == 4 # Bit packing: exactly matches width
assert row0[0] == 1
assert row0[3] == 4
assert len(row1) == 4
assert row1[0] == 5
assert row1[3] == 8
assert len(row2) == 4
assert row2[0] == 9
assert row2[3] == 12
def test_call_method(self):
"""Test direct element access via __call__"""
grid = Grid(3, 3, [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
])
# Test all positions
assert grid(0, 0) == 1
assert grid(0, 2) == 3
assert grid(1, 1) == 5
assert grid(2, 0) == 7
assert grid(2, 2) == 9
def test_set_method(self):
"""Test setting individual elements"""
grid = Grid(2, 3, 0) # Initialize with zeros
# Set some values
grid.set(0, 0, 10)
grid.set(0, 2, 30)
grid.set(1, 1, 50)
# Check that values were set correctly
assert grid(0, 0) == 10
assert grid(0, 1) == 0 # unchanged
assert grid(0, 2) == 30
assert grid(1, 0) == 0 # unchanged
assert grid(1, 1) == 50
assert grid(1, 2) == 0 # unchanged
def test_view_modifications(self):
"""Test that modifications through views affect the underlying data"""
grid = Grid(2, 3, [
[1, 2, 3],
[4, 5, 6]
])
# Get a view and modify it
row0 = grid[0]
row0[1] = 20
row0[2] = 30
# Check that underlying data changed
assert grid(0, 0) == 1 # unchanged
assert grid(0, 1) == 20 # changed
assert grid(0, 2) == 30 # changed
assert grid(1, 0) == 4 # unchanged
def test_view_isolation(self):
"""Test that different row views don't interfere"""
grid = Grid(3, 2, [
[1, 2],
[3, 4],
[5, 6]
])
# Get multiple views
row0 = grid[0]
row1 = grid[1]
row2 = grid[2]
# Modify different views
row0[0] = 10
row1[1] = 40
row2[0] = 50
# Check that modifications are isolated
assert grid(0, 0) == 10
assert grid(0, 1) == 2 # unchanged
assert grid(1, 0) == 3 # unchanged
assert grid(1, 1) == 40
assert grid(2, 0) == 50
assert grid(2, 1) == 6 # unchanged
def test_different_data_types(self):
"""Test grid with different data types"""
# String grid
str_grid = Grid(2, 2, [
['a', 'b'],
['c', 'd']
])
assert str_grid(0, 0) == 'a'
assert str_grid(1, 1) == 'd'
str_grid.set(0, 1, 'x')
assert str_grid(0, 1) == 'x'
# Float grid
float_grid = Grid(2, 2, 3.14)
assert float_grid(0, 0) == 3.14
assert float_grid(1, 1) == 3.14
def test_edge_cases(self):
"""Test edge cases and boundary conditions"""
# Single cell grid
single_grid = Grid(1, 1, 42)
assert len(single_grid) == 1
assert single_grid(0, 0) == 42
single_grid.set(0, 0, 99)
assert single_grid(0, 0) == 99
# Single row grid
row_grid = Grid(1, 5, [1, 2, 3, 4, 5])
assert len(row_grid) == 1
row = row_grid[0]
# Packer(5-1) has s=3, so row length is 1<<3=8, but we only use first 5
assert len(row) == 8 # Bit packing rounds up to power of 2
for j in range(5): # Only check the actual width
assert row[j] == j + 1
# Single column grid
col_grid = Grid(5, 1, [
[10],
[20],
[30],
[40],
[50]
])
assert len(col_grid) == 5
for i in range(5):
assert col_grid(i, 0) == (i + 1) * 10
def test_bounds_checking(self):
"""Test behavior with out-of-bounds access (implementation dependent)"""
grid = Grid(2, 3, [
[1, 2, 3],
[4, 5, 6]
])
# Valid access should work
assert grid(0, 0) == 1
assert grid(1, 2) == 6
# Views should have correct length (bit packed)
row0 = grid[0]
# Packer(3-1) has s=2, so row length is 1<<2=4
assert len(row0) == 4
# Out of bounds view access should raise IndexError
with pytest.raises(IndexError):
row0[4] # Row length is 4 due to bit packing
def test_large_grid(self):
"""Test with a larger grid to ensure performance and correctness"""
H, W = 50, 50
# Create grid with predictable pattern
grid_data = []
for i in range(H):
row = []
for j in range(W):
row.append(i * 100 + j)
grid_data.append(row)
grid = Grid(H, W, grid_data)
assert grid.H == H
assert grid.W == W
assert len(grid) == H
# Test random access
random.seed(42) # For reproducibility
for _ in range(100):
i = random.randint(0, H - 1)
j = random.randint(0, W - 1)
expected = i * 100 + j
assert grid(i, j) == expected
# Test row access
for i in range(min(10, H)): # Test first 10 rows
row = grid[i]
# Packer(50-1) has s=6, so row length is 1<<6=64
assert len(row) == 64 # Bit packing rounds up to power of 2
for j in range(W): # Only check actual width
assert row[j] == i * 100 + j
def test_grid_modification_patterns(self):
"""Test various modification patterns"""
grid = Grid(4, 4, 0)
# Fill diagonal
for i in range(4):
grid.set(i, i, i + 1)
# Check diagonal
for i in range(4):
assert grid(i, i) == i + 1
# Check non-diagonal elements are still 0
for j in range(4):
if i != j:
assert grid(i, j) == 0
# Modify through views
for i in range(4):
row = grid[i]
row[0] = 10 + i # First column
row[3] = 20 + i # Last column
# Check modifications
for i in range(4):
assert grid(i, 0) == 10 + i
assert grid(i, 3) == 20 + i
def test_grid_view_operations(self):
"""Test various operations on grid views"""
grid = Grid(3, 4, [
[4, 3, 2, 1],
[8, 7, 6, 5],
[12, 11, 10, 9]
])
# Test sorting a row
row0 = grid[0]
row0.sort()
# Check that row is now sorted
for j in range(3):
assert row0[j] <= row0[j + 1]
# Original grid should be modified
assert grid(0, 0) == 1
assert grid(0, 1) == 2
assert grid(0, 2) == 3
assert grid(0, 3) == 4
# Other rows should be unchanged
assert grid(1, 0) == 8
assert grid(2, 0) == 12
def test_memory_efficiency(self):
"""Test that grid uses bit packing efficiently"""
grid = Grid(4, 8, 0)
# Check that packer is set up correctly
assert grid.pkr is not None
assert grid.W == 8
# Packer(8-1) has s=3, so each row has 1<<3=8 slots (exactly matches width)
row = grid[0]
assert len(row) == 8
# The packer should efficiently encode coordinates
for i in range(4):
for j in range(8):
# Set unique values to test encoding/decoding
value = i * 10 + j
grid.set(i, j, value)
assert grid(i, j) == value
def test_initialization_edge_cases(self):
"""Test edge cases in initialization"""
# Small flat list (smaller than grid)
grid1 = Grid(2, 2, [42, 43, 44, 45]) # Provide enough elements
# Should map flat list to grid
expected_values = [42, 43, 44, 45]
for i in range(2):
for j in range(2):
assert grid1(i, j) == expected_values[i * 2 + j]
# Mixed type initialization (though not typical usage)
grid2 = Grid(2, 2, [
[1, 2],
[3, 4]
])
# Test that it works correctly
assert grid2(0, 0) == 1
assert grid2(1, 1) == 4
from cp_library.ds.grid.grid_cls import Grid
if __name__ == '__main__':
from cp_library.test.unittest_helper import run_verification_helper_unittest
run_verification_helper_unittest()# verification-helper: PROBLEM https://judge.yosupo.jp/problem/aplusb
import pytest
import random
class TestGrid:
"""
Tests for Grid class with bit-packed storage.
IMPORTANT: Grid uses Packer(W-1) for bit packing, which means:
- Packer(W-1) creates s = (W-1).bit_length()
- Each row has length 1 << s (next power of 2 >= W)
- Examples:
- W=3: Packer(2) → s=2 → row length = 4
- W=5: Packer(4) → s=3 → row length = 8
- W=8: Packer(7) → s=3 → row length = 8
- W=50: Packer(49) → s=6 → row length = 64
"""
def test_initialization_single_value(self):
"""Test initialization with a single value"""
grid = Grid(3, 4, 5)
assert grid.H == 3
assert grid.W == 4
assert len(grid) == 3
# All elements should be 5
for i in range(3):
for j in range(4):
assert grid(i, j) == 5
def test_initialization_flat_list(self):
"""Test initialization with a flat list"""
# List smaller than grid size
flat_list = [1, 2, 3, 4, 5, 6, 7, 8]
grid = Grid(2, 4, flat_list)
assert grid.H == 2
assert grid.W == 4
# Should map flat list to 2D grid row by row
expected = [
[1, 2, 3, 4],
[5, 6, 7, 8]
]
for i in range(2):
for j in range(4):
assert grid(i, j) == expected[i][j]
def test_initialization_2d_list(self):
"""Test initialization with a 2D list"""
grid_2d = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
grid = Grid(3, 3, grid_2d)
assert grid.H == 3
assert grid.W == 3
for i in range(3):
for j in range(3):
assert grid(i, j) == grid_2d[i][j]
def test_initialization_large_list(self):
"""Test initialization with a list larger than grid size"""
large_list = list(range(20))
grid = Grid(2, 3, large_list)
assert grid.H == 2
assert grid.W == 3
# Should use the list directly
for i in range(2):
for j in range(3):
# Direct access to packed array
expected_index = grid.pkr.enc(i, j)
assert grid(i, j) == large_list[expected_index]
def test_getitem_returns_view(self):
"""Test that __getitem__ returns a view of the row"""
grid_2d = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
grid = Grid(3, 4, grid_2d)
# Get row views
row0 = grid[0]
row1 = grid[1]
row2 = grid[2]
# Check row contents - Packer(4-1) has s=2, so row length is 1<<2=4
assert len(row0) == 4 # Bit packing: exactly matches width
assert row0[0] == 1
assert row0[3] == 4
assert len(row1) == 4
assert row1[0] == 5
assert row1[3] == 8
assert len(row2) == 4
assert row2[0] == 9
assert row2[3] == 12
def test_call_method(self):
"""Test direct element access via __call__"""
grid = Grid(3, 3, [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
])
# Test all positions
assert grid(0, 0) == 1
assert grid(0, 2) == 3
assert grid(1, 1) == 5
assert grid(2, 0) == 7
assert grid(2, 2) == 9
def test_set_method(self):
"""Test setting individual elements"""
grid = Grid(2, 3, 0) # Initialize with zeros
# Set some values
grid.set(0, 0, 10)
grid.set(0, 2, 30)
grid.set(1, 1, 50)
# Check that values were set correctly
assert grid(0, 0) == 10
assert grid(0, 1) == 0 # unchanged
assert grid(0, 2) == 30
assert grid(1, 0) == 0 # unchanged
assert grid(1, 1) == 50
assert grid(1, 2) == 0 # unchanged
def test_view_modifications(self):
"""Test that modifications through views affect the underlying data"""
grid = Grid(2, 3, [
[1, 2, 3],
[4, 5, 6]
])
# Get a view and modify it
row0 = grid[0]
row0[1] = 20
row0[2] = 30
# Check that underlying data changed
assert grid(0, 0) == 1 # unchanged
assert grid(0, 1) == 20 # changed
assert grid(0, 2) == 30 # changed
assert grid(1, 0) == 4 # unchanged
def test_view_isolation(self):
"""Test that different row views don't interfere"""
grid = Grid(3, 2, [
[1, 2],
[3, 4],
[5, 6]
])
# Get multiple views
row0 = grid[0]
row1 = grid[1]
row2 = grid[2]
# Modify different views
row0[0] = 10
row1[1] = 40
row2[0] = 50
# Check that modifications are isolated
assert grid(0, 0) == 10
assert grid(0, 1) == 2 # unchanged
assert grid(1, 0) == 3 # unchanged
assert grid(1, 1) == 40
assert grid(2, 0) == 50
assert grid(2, 1) == 6 # unchanged
def test_different_data_types(self):
"""Test grid with different data types"""
# String grid
str_grid = Grid(2, 2, [
['a', 'b'],
['c', 'd']
])
assert str_grid(0, 0) == 'a'
assert str_grid(1, 1) == 'd'
str_grid.set(0, 1, 'x')
assert str_grid(0, 1) == 'x'
# Float grid
float_grid = Grid(2, 2, 3.14)
assert float_grid(0, 0) == 3.14
assert float_grid(1, 1) == 3.14
def test_edge_cases(self):
"""Test edge cases and boundary conditions"""
# Single cell grid
single_grid = Grid(1, 1, 42)
assert len(single_grid) == 1
assert single_grid(0, 0) == 42
single_grid.set(0, 0, 99)
assert single_grid(0, 0) == 99
# Single row grid
row_grid = Grid(1, 5, [1, 2, 3, 4, 5])
assert len(row_grid) == 1
row = row_grid[0]
# Packer(5-1) has s=3, so row length is 1<<3=8, but we only use first 5
assert len(row) == 8 # Bit packing rounds up to power of 2
for j in range(5): # Only check the actual width
assert row[j] == j + 1
# Single column grid
col_grid = Grid(5, 1, [
[10],
[20],
[30],
[40],
[50]
])
assert len(col_grid) == 5
for i in range(5):
assert col_grid(i, 0) == (i + 1) * 10
def test_bounds_checking(self):
"""Test behavior with out-of-bounds access (implementation dependent)"""
grid = Grid(2, 3, [
[1, 2, 3],
[4, 5, 6]
])
# Valid access should work
assert grid(0, 0) == 1
assert grid(1, 2) == 6
# Views should have correct length (bit packed)
row0 = grid[0]
# Packer(3-1) has s=2, so row length is 1<<2=4
assert len(row0) == 4
# Out of bounds view access should raise IndexError
with pytest.raises(IndexError):
row0[4] # Row length is 4 due to bit packing
def test_large_grid(self):
"""Test with a larger grid to ensure performance and correctness"""
H, W = 50, 50
# Create grid with predictable pattern
grid_data = []
for i in range(H):
row = []
for j in range(W):
row.append(i * 100 + j)
grid_data.append(row)
grid = Grid(H, W, grid_data)
assert grid.H == H
assert grid.W == W
assert len(grid) == H
# Test random access
random.seed(42) # For reproducibility
for _ in range(100):
i = random.randint(0, H - 1)
j = random.randint(0, W - 1)
expected = i * 100 + j
assert grid(i, j) == expected
# Test row access
for i in range(min(10, H)): # Test first 10 rows
row = grid[i]
# Packer(50-1) has s=6, so row length is 1<<6=64
assert len(row) == 64 # Bit packing rounds up to power of 2
for j in range(W): # Only check actual width
assert row[j] == i * 100 + j
def test_grid_modification_patterns(self):
"""Test various modification patterns"""
grid = Grid(4, 4, 0)
# Fill diagonal
for i in range(4):
grid.set(i, i, i + 1)
# Check diagonal
for i in range(4):
assert grid(i, i) == i + 1
# Check non-diagonal elements are still 0
for j in range(4):
if i != j:
assert grid(i, j) == 0
# Modify through views
for i in range(4):
row = grid[i]
row[0] = 10 + i # First column
row[3] = 20 + i # Last column
# Check modifications
for i in range(4):
assert grid(i, 0) == 10 + i
assert grid(i, 3) == 20 + i
def test_grid_view_operations(self):
"""Test various operations on grid views"""
grid = Grid(3, 4, [
[4, 3, 2, 1],
[8, 7, 6, 5],
[12, 11, 10, 9]
])
# Test sorting a row
row0 = grid[0]
row0.sort()
# Check that row is now sorted
for j in range(3):
assert row0[j] <= row0[j + 1]
# Original grid should be modified
assert grid(0, 0) == 1
assert grid(0, 1) == 2
assert grid(0, 2) == 3
assert grid(0, 3) == 4
# Other rows should be unchanged
assert grid(1, 0) == 8
assert grid(2, 0) == 12
def test_memory_efficiency(self):
"""Test that grid uses bit packing efficiently"""
grid = Grid(4, 8, 0)
# Check that packer is set up correctly
assert grid.pkr is not None
assert grid.W == 8
# Packer(8-1) has s=3, so each row has 1<<3=8 slots (exactly matches width)
row = grid[0]
assert len(row) == 8
# The packer should efficiently encode coordinates
for i in range(4):
for j in range(8):
# Set unique values to test encoding/decoding
value = i * 10 + j
grid.set(i, j, value)
assert grid(i, j) == value
def test_initialization_edge_cases(self):
"""Test edge cases in initialization"""
# Small flat list (smaller than grid)
grid1 = Grid(2, 2, [42, 43, 44, 45]) # Provide enough elements
# Should map flat list to grid
expected_values = [42, 43, 44, 45]
for i in range(2):
for j in range(2):
assert grid1(i, j) == expected_values[i * 2 + j]
# Mixed type initialization (though not typical usage)
grid2 = Grid(2, 2, [
[1, 2],
[3, 4]
])
# Test that it works correctly
assert grid2(0, 0) == 1
assert grid2(1, 1) == 4
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
import typing
from collections import deque
from numbers import Number
from types import GenericAlias
from typing import Callable, Collection, Iterator, Union
import os
import sys
from io import BytesIO, IOBase
class FastIO(IOBase):
BUFSIZE = 8192
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
BUFSIZE = self.BUFSIZE
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b: break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
BUFSIZE = self.BUFSIZE
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
stdin: 'IOWrapper' = None
stdout: 'IOWrapper' = None
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
def write(self, s):
return self.buffer.write(s.encode("ascii"))
def read(self):
return self.buffer.read().decode("ascii")
def readline(self):
return self.buffer.readline().decode("ascii")
try:
sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)
except:
pass
from typing import TypeVar
_S = TypeVar('S')
_T = TypeVar('T')
_U = TypeVar('U')
class TokenStream(Iterator):
stream = IOWrapper.stdin
def __init__(self):
self.queue = deque()
def __next__(self):
if not self.queue: self.queue.extend(self._line())
return self.queue.popleft()
def wait(self):
if not self.queue: self.queue.extend(self._line())
while self.queue: yield
def _line(self):
return TokenStream.stream.readline().split()
def line(self):
if self.queue:
A = list(self.queue)
self.queue.clear()
return A
return self._line()
TokenStream.default = TokenStream()
class CharStream(TokenStream):
def _line(self):
return TokenStream.stream.readline().rstrip()
CharStream.default = CharStream()
ParseFn = Callable[[TokenStream],_T]
class Parser:
def __init__(self, spec: Union[type[_T],_T]):
self.parse = Parser.compile(spec)
def __call__(self, ts: TokenStream) -> _T:
return self.parse(ts)
@staticmethod
def compile_type(cls: type[_T], args = ()) -> _T:
if issubclass(cls, Parsable):
return cls.compile(*args)
elif issubclass(cls, (Number, str)):
def parse(ts: TokenStream): return cls(next(ts))
return parse
elif issubclass(cls, tuple):
return Parser.compile_tuple(cls, args)
elif issubclass(cls, Collection):
return Parser.compile_collection(cls, args)
elif callable(cls):
def parse(ts: TokenStream):
return cls(next(ts))
return parse
else:
raise NotImplementedError()
@staticmethod
def compile(spec: Union[type[_T],_T]=int) -> ParseFn[_T]:
if isinstance(spec, (type, GenericAlias)):
cls = typing.get_origin(spec) or spec
args = typing.get_args(spec) or tuple()
return Parser.compile_type(cls, args)
elif isinstance(offset := spec, Number):
cls = type(spec)
def parse(ts: TokenStream): return cls(next(ts)) + offset
return parse
elif isinstance(args := spec, tuple):
return Parser.compile_tuple(type(spec), args)
elif isinstance(args := spec, Collection):
return Parser.compile_collection(type(spec), args)
elif isinstance(fn := spec, Callable):
def parse(ts: TokenStream): return fn(next(ts))
return parse
else:
raise NotImplementedError()
@staticmethod
def compile_line(cls: _T, spec=int) -> ParseFn[_T]:
if spec is int:
fn = Parser.compile(spec)
def parse(ts: TokenStream): return cls([int(token) for token in ts.line()])
return parse
else:
fn = Parser.compile(spec)
def parse(ts: TokenStream): return cls([fn(ts) for _ in ts.wait()])
return parse
@staticmethod
def compile_repeat(cls: _T, spec, N) -> ParseFn[_T]:
fn = Parser.compile(spec)
def parse(ts: TokenStream): return cls([fn(ts) for _ in range(N)])
return parse
@staticmethod
def compile_children(cls: _T, specs) -> ParseFn[_T]:
fns = tuple((Parser.compile(spec) for spec in specs))
def parse(ts: TokenStream): return cls([fn(ts) for fn in fns])
return parse
@staticmethod
def compile_tuple(cls: type[_T], specs) -> ParseFn[_T]:
if isinstance(specs, (tuple,list)) and len(specs) == 2 and specs[1] is ...:
return Parser.compile_line(cls, specs[0])
else:
return Parser.compile_children(cls, specs)
@staticmethod
def compile_collection(cls, specs):
if not specs or len(specs) == 1 or isinstance(specs, set):
return Parser.compile_line(cls, *specs)
elif (isinstance(specs, (tuple,list)) and len(specs) == 2 and isinstance(specs[1], int)):
return Parser.compile_repeat(cls, specs[0], specs[1])
else:
raise NotImplementedError()
class Parsable:
@classmethod
def compile(cls):
def parser(ts: TokenStream): return cls(next(ts))
return parser
@classmethod
def __class_getitem__(cls, item):
return GenericAlias(cls, item)
from typing import Generic
def list_find(lst: list, value, start = 0, stop = sys.maxsize):
try:
return lst.index(value, start, stop)
except:
return -1
class view(Generic[_T]):
__slots__ = 'A', 'l', 'r'
def __init__(V, A: list[_T], l: int, r: int): V.A, V.l, V.r = A, l, r
def __len__(V): return V.r - V.l
def __getitem__(V, i: int):
if 0 <= i < V.r - V.l: return V.A[V.l+i]
else: raise IndexError
def __setitem__(V, i: int, v: _T): V.A[V.l+i] = v
def __contains__(V, v: _T): return list_find(V.A, v, V.l, V.r) != -1
def set_range(V, l: int, r: int): V.l, V.r = l, r
def index(V, v: _T): return V.A.index(v, V.l, V.r) - V.l
def reverse(V):
l, r = V.l, V.r-1
while l < r: V.A[l], V.A[r] = V.A[r], V.A[l]; l += 1; r -= 1
def sort(V, /, *args, **kwargs):
A = V.A[V.l:V.r]; A.sort(*args, **kwargs)
for i,a in enumerate(A,V.l): V.A[i] = a
def pop(V): V.r -= 1; return V.A[V.r]
def append(V, v: _T): V.A[V.r] = v; V.r += 1
def popleft(V): V.l += 1; return V.A[V.l-1]
def appendleft(V, v: _T): V.l -= 1; V.A[V.l] = v;
def validate(V): return 0 <= V.l <= V.r <= len(V.A)
class Packer:
__slots__ = 's', 'm'
def __init__(P, mx: int): P.s = mx.bit_length(); P.m = (1 << P.s) - 1
def enc(P, a: int, b: int): return a << P.s | b
def dec(P, x: int) -> tuple[int, int]: return x >> P.s, x & P.m
def enumerate(P, A, reverse=False): P.ienumerate(A:=list(A), reverse); return A
def ienumerate(P, A, reverse=False):
if reverse:
for i,a in enumerate(A): A[i] = P.enc(-a, i)
else:
for i,a in enumerate(A): A[i] = P.enc(a, i)
def indices(P, A: list[int]): P.iindices(A:=list(A)); return A
def iindices(P, A):
for i,a in enumerate(A): A[i] = P.m&a
class Grid(Generic[_T], Parsable):
__slots__ = 'pkr', 'size', 'H', 'W', 'A'
def __init__(G, H: int, W: int, A: Union[_T, list[_T], list[list[_T]]], pkr = None):
G.pkr = pkr or Packer(W-1); G.size = H << G.pkr.s; G.H, G.W = H, W
if isinstance(A, list):
if isinstance(A[0], list):
G.A = [A[0][0]]*G.size
for i in range(H):
ii = i << G.pkr.s
for j in range(W): G.A[ii|j] = A[i][j]
elif len(A) < G.size:
G.A = [A[0]]*G.size
for i in range(H):
ii = i << G.pkr.s
for j in range(W): G.A[ii|j] = A[i*W+j]
else:
G.A = A
else:
G.A = [A] * G.size
def __len__(G): return G.H
def __getitem__(G, i: int):
if 0 <= i < G.H: return view(G.A, i<<G.pkr.s, (i+1)<<G.pkr.s)
else: raise IndexError
def __call__(G, i: int, j: int): return G.A[G.pkr.enc(i,j)]
def set(G, i: int, j: int, v: _T): G.A[G.pkr.enc(i,j)] = v
@classmethod
def compile(cls, H: int, W: int, T: type = int):
pkr = Packer(W-1); size = H << pkr.s
if T is int:
def parse(ts: TokenStream):
A = [0]*size
for i in range(H):
for j,s in ts.line(): A[pkr.enc(i,j)] = int(s)
return cls(H, W, A, pkr)
elif T is str:
def parse(ts: TokenStream):
A = ['']*size
for i in range(H):
for j,s in ts.line(): A[pkr.enc(i,j)] = s
return cls(H, W, A, pkr)
else:
elm = Parser.compile(T)
def parse(ts: TokenStream):
A = [None]*size
for i in range(H):
for j in range(W): A[pkr.enc(i,j)] = elm(ts)
return cls(H, W, A, pkr)
return parse
if __name__ == '__main__':
"""
Helper for making unittest files compatible with verification-helper.
This module provides a helper function to run a dummy Library Checker test
so that unittest files can be verified by oj-verify.
"""
def run_verification_helper_unittest():
"""
Run a dummy Library Checker test for verification-helper compatibility.
This function should be called in the __main__ block of unittest files
that need to be compatible with verification-helper.
The function:
1. Reads A and B from input
2. Writes A+B to output
3. If the result is the expected value (1198300249), runs pytest
4. Exits with the pytest result code
"""
from typing import Type, Union, overload
@overload
def read() -> list[int]: ...
@overload
def read(spec: Type[_T], char=False) -> _T: ...
@overload
def read(spec: _U, char=False) -> _U: ...
@overload
def read(*specs: Type[_T], char=False) -> tuple[_T, ...]: ...
@overload
def read(*specs: _U, char=False) -> tuple[_U, ...]: ...
def read(*specs: Union[Type[_T],_U], char=False):
if not char and not specs: return [int(s) for s in TokenStream.default.line()]
parser: _T = Parser.compile(specs[0] if len(specs) == 1 else specs)
return parser(CharStream.default if char else TokenStream.default)
def write(*args, **kwargs):
'''Prints the values to a stream, or to stdout_fast by default.'''
sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
at_start = True
for x in args:
if not at_start:
file.write(sep)
file.write(str(x))
at_start = False
file.write(kwargs.pop("end", "\n"))
if kwargs.pop("flush", False):
file.flush()
A, B = read()
write(C := A + B)
if C != 1198300249:
sys.exit(0)
import io
from contextlib import redirect_stdout, redirect_stderr
# Capture all output during test execution
output = io.StringIO()
with redirect_stdout(output), redirect_stderr(output):
# Get the calling module's file path
frame = sys._getframe(1)
test_file = frame.f_globals.get('__file__')
if test_file is None:
test_file = sys.argv[0]
result = pytest.main([test_file])
if result != 0:
print(output.getvalue())
sys.exit(result)
run_verification_helper_unittest()