cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unittests/ds/view/csr2_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/alg/iter/arg/argsort_ranged_fn.py
- cp_library/alg/iter/sort/isort_ranged_fn.py
- cp_library/bit/pack/packer_cls.py
- cp_library/ds/view/csr2_cls.py
- cp_library/ds/view/view2_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 TestCSR2:
def test_initialization(self):
"""Test basic initialization of CSR2"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
assert csr2.A is A
assert csr2.B is B
assert csr2.O is O
assert len(csr2) == 3
def test_len(self):
"""Test __len__ method"""
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50]
O = [0, 2, 3, 5] # 3 rows: [(1,10),(2,20)], [(3,30)], [(4,40),(5,50)]
csr2 = CSR2(A, B, O)
assert len(csr2) == 3
# Empty CSR2
empty_csr2 = CSR2([], [], [0])
assert len(empty_csr2) == 0
def test_getitem(self):
"""Test __getitem__ method (returns temporary view2)"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Test temporary access - each call returns the same view object but points to different rows
# Test row 0
row = csr2[0]
assert len(row) == 2
assert row[0] == (1, 10)
assert row[1] == (2, 20)
# Test row 1 - same view object, different range
row = csr2[1]
assert len(row) == 2
assert row[0] == (3, 30)
assert row[1] == (4, 40)
# Test row 2 - same view object, different range
row = csr2[2]
assert len(row) == 2
assert row[0] == (5, 50)
assert row[1] == (6, 60)
def test_call(self):
"""Test __call__ method (direct element access)"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Direct access to elements
assert csr2(0, 0) == (1, 10)
assert csr2(0, 1) == (2, 20)
assert csr2(1, 0) == (3, 30)
assert csr2(1, 1) == (4, 40)
assert csr2(2, 0) == (5, 50)
assert csr2(2, 1) == (6, 60)
def test_set(self):
"""Test set method"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Modify elements
csr2.set(0, 0, (15, 150))
csr2.set(1, 1, (45, 450))
csr2.set(2, 0, (55, 550))
assert A == [15, 2, 3, 45, 55, 6]
assert B == [150, 20, 30, 450, 550, 60]
assert csr2(0, 0) == (15, 150)
assert csr2(1, 1) == (45, 450)
assert csr2(2, 0) == (55, 550)
def test_getitem_method(self):
"""Test __getitem__ method (creates new view2)"""
A = [1, 2, 3, 4, 5, 6, 7, 8]
B = [10, 20, 30, 40, 50, 60, 70, 80]
O = [0, 3, 5, 8] # 3 rows: [(1,10),(2,20),(3,30)], [(4,40),(5,50)], [(6,60),(7,70),(8,80)]
csr2 = CSR2(A, B, O)
# Create views for each row
view0 = csr2[0]
view1 = csr2[1]
view2 = csr2[2]
assert len(view0) == 3
assert view0[0] == (1, 10)
assert view0[2] == (3, 30)
assert len(view1) == 2
assert view1[0] == (4, 40)
assert view1[1] == (5, 50)
assert len(view2) == 3
assert view2[0] == (6, 60)
assert view2[2] == (8, 80)
def test_bucketize(self):
"""Test bucketize class method"""
# Create buckets: bucket 0 gets [(1,11),(3,33)], bucket 1 gets [(2,22)], bucket 2 gets [(4,44),(5,55)]
N = 3
K = [0, 1, 0, 2, 2] # Keys indicating which bucket each value goes to
V = [1, 2, 3, 4, 5] # Values for first array
W = [11, 22, 33, 44, 55] # Values for second array
csr2 = CSR2.bucketize(N, K, V, W)
assert len(csr2) == 3
# Check bucket 0: should contain [(3,33), (1,11)] (reverse order due to algorithm)
row0 = csr2[0]
assert len(row0) == 2
assert set([row0[0], row0[1]]) == {(1, 11), (3, 33)}
# Check bucket 1: should contain [(2,22)]
row1 = csr2[1]
assert len(row1) == 1
assert row1[0] == (2, 22)
# Check bucket 2: should contain [(5,55), (4,44)] (reverse order)
row2 = csr2[2]
assert len(row2) == 2
assert set([row2[0], row2[1]]) == {(4, 44), (5, 55)}
def test_empty_rows(self):
"""Test CSR2 with empty rows"""
A = [1, 2, 3, 4]
B = [10, 20, 30, 40]
O = [0, 2, 2, 4] # 3 rows: [(1,10),(2,20)], [], [(3,30),(4,40)]
csr2 = CSR2(A, B, O)
assert len(csr2) == 3
# Row 0: [(1,10),(2,20)]
row0 = csr2[0]
assert len(row0) == 2
assert row0[0] == (1, 10)
assert row0[1] == (2, 20)
# Row 1: empty
row1 = csr2[1]
assert len(row1) == 0
# Row 2: [(3,30),(4,40)]
row2 = csr2[2]
assert len(row2) == 2
assert row2[0] == (3, 30)
assert row2[1] == (4, 40)
def test_single_element_rows(self):
"""Test CSR2 with single element rows"""
A = [1, 2, 3]
B = [10, 20, 30]
O = [0, 1, 2, 3] # 3 rows: [(1,10)], [(2,20)], [(3,30)]
csr2 = CSR2(A, B, O)
assert len(csr2) == 3
for i in range(3):
row = csr2[i]
assert len(row) == 1
assert row[0] == (i + 1, (i + 1) * 10)
assert csr2(i, 0) == (i + 1, (i + 1) * 10)
def test_view_modifications(self):
"""Test that view modifications affect the underlying data"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Get a view and modify it
row1 = csr2[1]
row1[0] = (30, 300)
row1[1] = (40, 400)
# Check that underlying data changed
assert A == [1, 2, 30, 40, 5, 6]
assert B == [10, 20, 300, 400, 50, 60]
assert csr2(1, 0) == (30, 300)
assert csr2(1, 1) == (40, 400)
def test_view_operations(self):
"""Test various view operations"""
A = [5, 3, 1, 4, 2, 6]
B = [50, 30, 10, 40, 20, 60]
O = [0, 3, 6] # 2 rows: [(5,50),(3,30),(1,10)], [(4,40),(2,20),(6,60)]
csr2 = CSR2(A, B, O)
# Get views and operate on them
row0 = csr2[0]
row0.sort()
assert A[:3] == [1, 3, 5]
assert B[:3] == [10, 30, 50]
row1 = csr2[1]
row1.reverse()
assert A[3:] == [6, 2, 4]
assert B[3:] == [60, 20, 40]
def test_view_creation_behavior(self):
"""Test that __getitem__ creates new view objects each time"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# __getitem__ creates new view objects each time
view1 = csr2[0] # New view of row 0
view2 = csr2[0] # Another new view of row 0
# Should be different objects but point to the same data
assert view1 is not view2 # Different objects
# But should have the same data
assert len(view1) == len(view2) == 2
assert view1[0] == view2[0] == (1, 10) # Row 0 data
assert view1[1] == view2[1] == (2, 20) # Row 0 data
# Views of different rows should also be independent
row0_view = csr2[0]
row1_view = csr2[1]
assert row0_view is not row1_view # Different objects
assert len(row0_view) == 2
assert row0_view[0] == (1, 10) # Row 0 data
assert len(row1_view) == 2
assert row1_view[0] == (3, 30) # Row 1 data
def test_large_csr2(self):
"""Test CSR2 with larger data"""
# Create 100 rows with 10 elements each
A = list(range(1000))
B = list(range(1000, 2000))
O = [i * 10 for i in range(101)] # 100 rows
csr2 = CSR2(A, B, O)
assert len(csr2) == 100
# Test random access
assert csr2(50, 5) == (505, 1505)
assert csr2(99, 9) == (999, 1999)
# Test view length
for i in range(100):
assert len(csr2[i]) == 10
def test_bucketize_edge_cases(self):
"""Test bucketize with edge cases"""
# All elements go to the same bucket
N = 3
K = [1, 1, 1, 1]
V = [10, 20, 30, 40]
W = [100, 200, 300, 400]
csr2 = CSR2.bucketize(N, K, V, W)
assert len(csr2) == 3
# Bucket 0 should be empty
assert len(csr2[0]) == 0
# Bucket 1 should have all elements
assert len(csr2[1]) == 4
# Bucket 2 should be empty
assert len(csr2[2]) == 0
def test_bucketize_empty(self):
"""Test bucketize with empty input"""
N = 3
K = []
V = []
W = []
csr2 = CSR2.bucketize(N, K, V, W)
assert len(csr2) == 3
# All buckets should be empty
for i in range(3):
assert len(csr2[i]) == 0
def test_different_data_types(self):
"""Test CSR2 with different data types"""
# Mixed types
A = [1, 2, 3, 4, 5, 6]
B = ['a', 'b', 'c', 'd', 'e', 'f']
O = [0, 2, 4, 6]
csr2 = CSR2(A, B, O)
assert csr2(0, 0) == (1, 'a')
assert csr2(1, 1) == (4, 'd')
assert csr2(2, 0) == (5, 'e')
# Float types
A_float = [1.1, 2.2, 3.3, 4.4]
B_float = [10.1, 20.2, 30.3, 40.4]
O_float = [0, 2, 4]
csr2_float = CSR2(A_float, B_float, O_float)
assert csr2_float(0, 0) == (1.1, 10.1)
assert csr2_float(1, 1) == (4.4, 40.4)
def test_bounds_checking(self):
"""Test that appropriate errors are raised for out-of-bounds access"""
A = [1, 2, 3, 4]
B = [10, 20, 30, 40]
O = [0, 2, 4] # 2 rows: [(1,10),(2,20)], [(3,30),(4,40)]
csr2 = CSR2(A, B, O)
# These should work
assert csr2(0, 1) == (2, 20)
assert csr2(1, 0) == (3, 30)
# Out of bounds row access should raise IndexError when accessing the view
row = csr2[0]
with pytest.raises(IndexError):
row[2] # Row 0 only has 2 elements (indices 0, 1)
def test_random_operations(self):
"""Test random operations for robustness"""
random.seed(42) # For reproducibility
# Create random CSR2 structure
num_rows = 50
total_elements = 500
A = [random.randint(1, 1000) for _ in range(total_elements)]
B = [random.randint(1000, 2000) for _ in range(total_elements)]
# Generate random row sizes
O = [0]
remaining = total_elements
for i in range(num_rows - 1):
if remaining > 0:
row_size = random.randint(0, min(20, remaining))
O.append(O[-1] + row_size)
remaining -= row_size
else:
O.append(O[-1])
O.append(total_elements)
csr2 = CSR2(A, B, O)
assert len(csr2) == num_rows
# Perform random operations
for _ in range(100):
row_idx = random.randint(0, num_rows - 1)
row = csr2[row_idx]
if len(row) > 0:
col_idx = random.randint(0, len(row) - 1)
# Read operation
val1 = csr2(row_idx, col_idx)
val2 = row[col_idx]
assert val1 == val2
# Write operation
new_val = (random.randint(2000, 3000), random.randint(3000, 4000))
csr2.set(row_idx, col_idx, new_val)
assert csr2(row_idx, col_idx) == new_val
assert row[col_idx] == new_val
def test_view_isolation(self):
"""Test that different views don't interfere with each other"""
A = [1, 2, 3, 4, 5, 6, 7, 8]
B = [10, 20, 30, 40, 50, 60, 70, 80]
O = [0, 3, 5, 8] # 3 rows: [(1,10),(2,20),(3,30)], [(4,40),(5,50)], [(6,60),(7,70),(8,80)]
csr2 = CSR2(A, B, O)
# Get multiple views
view0 = csr2[0]
view1 = csr2[1]
view2 = csr2[2]
# Modify through different views
view0[0] = (10, 100)
view1[1] = (50, 500)
view2[2] = (80, 800)
# Check that modifications are isolated and correct
assert A == [10, 2, 3, 4, 50, 6, 7, 80]
assert B == [100, 20, 30, 40, 500, 60, 70, 800]
assert view0[0] == (10, 100)
assert view1[1] == (50, 500)
assert view2[2] == (80, 800)
# Other elements should be unchanged
assert view0[1] == (2, 20)
assert view1[0] == (4, 40)
assert view2[0] == (6, 60)
def test_bucketize_order_preservation(self):
"""Test bucketize behavior with element ordering"""
N = 2
K = [0, 1, 0, 1, 0] # Alternating buckets
V = [1, 2, 3, 4, 5]
W = [10, 20, 30, 40, 50]
csr2 = CSR2.bucketize(N, K, V, W)
# Bucket 0 should contain elements from positions 0, 2, 4
# The bucketize algorithm processes in reverse order, so elements are inserted last-to-first
row0 = csr2[0]
assert len(row0) == 3
# Elements should be in reverse insertion order: (5,50), (3,30), (1,10)
elements_bucket0 = [row0[i] for i in range(len(row0))]
assert set(elements_bucket0) == {(1, 10), (3, 30), (5, 50)}
# Bucket 1 should contain elements from positions 1, 3
row1 = csr2[1]
assert len(row1) == 2
# Elements should be in reverse insertion order: (4,40), (2,20)
elements_bucket1 = [row1[i] for i in range(len(row1))]
assert set(elements_bucket1) == {(2, 20), (4, 40)}
def test_complex_operations_sequence(self):
"""Test complex sequence of operations using persistent views"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
O = [0, 3, 6, 9] # 3 rows of 3 elements each
csr2 = CSR2(A, B, O)
# Get views and perform operations
row0 = csr2[0]
row1 = csr2[1]
# Sort first row
row0.sort()
assert A[:3] == [1, 2, 3]
assert B[:3] == [10, 20, 30]
# Reverse second row
row1.reverse()
assert A[3:6] == [6, 5, 4]
assert B[3:6] == [60, 50, 40]
# Modify third row using set method
csr2.set(2, 0, (90, 900))
csr2.set(2, 1, (80, 800))
csr2.set(2, 2, (70, 700))
assert A[6:9] == [90, 80, 70]
assert B[6:9] == [900, 800, 700]
# Verify final state
assert csr2(0, 0) == (1, 10)
assert csr2(1, 0) == (6, 60)
assert csr2(2, 0) == (90, 900)
from cp_library.ds.view.csr2_cls import CSR2
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 TestCSR2:
def test_initialization(self):
"""Test basic initialization of CSR2"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
assert csr2.A is A
assert csr2.B is B
assert csr2.O is O
assert len(csr2) == 3
def test_len(self):
"""Test __len__ method"""
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50]
O = [0, 2, 3, 5] # 3 rows: [(1,10),(2,20)], [(3,30)], [(4,40),(5,50)]
csr2 = CSR2(A, B, O)
assert len(csr2) == 3
# Empty CSR2
empty_csr2 = CSR2([], [], [0])
assert len(empty_csr2) == 0
def test_getitem(self):
"""Test __getitem__ method (returns temporary view2)"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Test temporary access - each call returns the same view object but points to different rows
# Test row 0
row = csr2[0]
assert len(row) == 2
assert row[0] == (1, 10)
assert row[1] == (2, 20)
# Test row 1 - same view object, different range
row = csr2[1]
assert len(row) == 2
assert row[0] == (3, 30)
assert row[1] == (4, 40)
# Test row 2 - same view object, different range
row = csr2[2]
assert len(row) == 2
assert row[0] == (5, 50)
assert row[1] == (6, 60)
def test_call(self):
"""Test __call__ method (direct element access)"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Direct access to elements
assert csr2(0, 0) == (1, 10)
assert csr2(0, 1) == (2, 20)
assert csr2(1, 0) == (3, 30)
assert csr2(1, 1) == (4, 40)
assert csr2(2, 0) == (5, 50)
assert csr2(2, 1) == (6, 60)
def test_set(self):
"""Test set method"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Modify elements
csr2.set(0, 0, (15, 150))
csr2.set(1, 1, (45, 450))
csr2.set(2, 0, (55, 550))
assert A == [15, 2, 3, 45, 55, 6]
assert B == [150, 20, 30, 450, 550, 60]
assert csr2(0, 0) == (15, 150)
assert csr2(1, 1) == (45, 450)
assert csr2(2, 0) == (55, 550)
def test_getitem_method(self):
"""Test __getitem__ method (creates new view2)"""
A = [1, 2, 3, 4, 5, 6, 7, 8]
B = [10, 20, 30, 40, 50, 60, 70, 80]
O = [0, 3, 5, 8] # 3 rows: [(1,10),(2,20),(3,30)], [(4,40),(5,50)], [(6,60),(7,70),(8,80)]
csr2 = CSR2(A, B, O)
# Create views for each row
view0 = csr2[0]
view1 = csr2[1]
view2 = csr2[2]
assert len(view0) == 3
assert view0[0] == (1, 10)
assert view0[2] == (3, 30)
assert len(view1) == 2
assert view1[0] == (4, 40)
assert view1[1] == (5, 50)
assert len(view2) == 3
assert view2[0] == (6, 60)
assert view2[2] == (8, 80)
def test_bucketize(self):
"""Test bucketize class method"""
# Create buckets: bucket 0 gets [(1,11),(3,33)], bucket 1 gets [(2,22)], bucket 2 gets [(4,44),(5,55)]
N = 3
K = [0, 1, 0, 2, 2] # Keys indicating which bucket each value goes to
V = [1, 2, 3, 4, 5] # Values for first array
W = [11, 22, 33, 44, 55] # Values for second array
csr2 = CSR2.bucketize(N, K, V, W)
assert len(csr2) == 3
# Check bucket 0: should contain [(3,33), (1,11)] (reverse order due to algorithm)
row0 = csr2[0]
assert len(row0) == 2
assert set([row0[0], row0[1]]) == {(1, 11), (3, 33)}
# Check bucket 1: should contain [(2,22)]
row1 = csr2[1]
assert len(row1) == 1
assert row1[0] == (2, 22)
# Check bucket 2: should contain [(5,55), (4,44)] (reverse order)
row2 = csr2[2]
assert len(row2) == 2
assert set([row2[0], row2[1]]) == {(4, 44), (5, 55)}
def test_empty_rows(self):
"""Test CSR2 with empty rows"""
A = [1, 2, 3, 4]
B = [10, 20, 30, 40]
O = [0, 2, 2, 4] # 3 rows: [(1,10),(2,20)], [], [(3,30),(4,40)]
csr2 = CSR2(A, B, O)
assert len(csr2) == 3
# Row 0: [(1,10),(2,20)]
row0 = csr2[0]
assert len(row0) == 2
assert row0[0] == (1, 10)
assert row0[1] == (2, 20)
# Row 1: empty
row1 = csr2[1]
assert len(row1) == 0
# Row 2: [(3,30),(4,40)]
row2 = csr2[2]
assert len(row2) == 2
assert row2[0] == (3, 30)
assert row2[1] == (4, 40)
def test_single_element_rows(self):
"""Test CSR2 with single element rows"""
A = [1, 2, 3]
B = [10, 20, 30]
O = [0, 1, 2, 3] # 3 rows: [(1,10)], [(2,20)], [(3,30)]
csr2 = CSR2(A, B, O)
assert len(csr2) == 3
for i in range(3):
row = csr2[i]
assert len(row) == 1
assert row[0] == (i + 1, (i + 1) * 10)
assert csr2(i, 0) == (i + 1, (i + 1) * 10)
def test_view_modifications(self):
"""Test that view modifications affect the underlying data"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# Get a view and modify it
row1 = csr2[1]
row1[0] = (30, 300)
row1[1] = (40, 400)
# Check that underlying data changed
assert A == [1, 2, 30, 40, 5, 6]
assert B == [10, 20, 300, 400, 50, 60]
assert csr2(1, 0) == (30, 300)
assert csr2(1, 1) == (40, 400)
def test_view_operations(self):
"""Test various view operations"""
A = [5, 3, 1, 4, 2, 6]
B = [50, 30, 10, 40, 20, 60]
O = [0, 3, 6] # 2 rows: [(5,50),(3,30),(1,10)], [(4,40),(2,20),(6,60)]
csr2 = CSR2(A, B, O)
# Get views and operate on them
row0 = csr2[0]
row0.sort()
assert A[:3] == [1, 3, 5]
assert B[:3] == [10, 30, 50]
row1 = csr2[1]
row1.reverse()
assert A[3:] == [6, 2, 4]
assert B[3:] == [60, 20, 40]
def test_view_creation_behavior(self):
"""Test that __getitem__ creates new view objects each time"""
A = [1, 2, 3, 4, 5, 6]
B = [10, 20, 30, 40, 50, 60]
O = [0, 2, 4, 6] # 3 rows: [(1,10),(2,20)], [(3,30),(4,40)], [(5,50),(6,60)]
csr2 = CSR2(A, B, O)
# __getitem__ creates new view objects each time
view1 = csr2[0] # New view of row 0
view2 = csr2[0] # Another new view of row 0
# Should be different objects but point to the same data
assert view1 is not view2 # Different objects
# But should have the same data
assert len(view1) == len(view2) == 2
assert view1[0] == view2[0] == (1, 10) # Row 0 data
assert view1[1] == view2[1] == (2, 20) # Row 0 data
# Views of different rows should also be independent
row0_view = csr2[0]
row1_view = csr2[1]
assert row0_view is not row1_view # Different objects
assert len(row0_view) == 2
assert row0_view[0] == (1, 10) # Row 0 data
assert len(row1_view) == 2
assert row1_view[0] == (3, 30) # Row 1 data
def test_large_csr2(self):
"""Test CSR2 with larger data"""
# Create 100 rows with 10 elements each
A = list(range(1000))
B = list(range(1000, 2000))
O = [i * 10 for i in range(101)] # 100 rows
csr2 = CSR2(A, B, O)
assert len(csr2) == 100
# Test random access
assert csr2(50, 5) == (505, 1505)
assert csr2(99, 9) == (999, 1999)
# Test view length
for i in range(100):
assert len(csr2[i]) == 10
def test_bucketize_edge_cases(self):
"""Test bucketize with edge cases"""
# All elements go to the same bucket
N = 3
K = [1, 1, 1, 1]
V = [10, 20, 30, 40]
W = [100, 200, 300, 400]
csr2 = CSR2.bucketize(N, K, V, W)
assert len(csr2) == 3
# Bucket 0 should be empty
assert len(csr2[0]) == 0
# Bucket 1 should have all elements
assert len(csr2[1]) == 4
# Bucket 2 should be empty
assert len(csr2[2]) == 0
def test_bucketize_empty(self):
"""Test bucketize with empty input"""
N = 3
K = []
V = []
W = []
csr2 = CSR2.bucketize(N, K, V, W)
assert len(csr2) == 3
# All buckets should be empty
for i in range(3):
assert len(csr2[i]) == 0
def test_different_data_types(self):
"""Test CSR2 with different data types"""
# Mixed types
A = [1, 2, 3, 4, 5, 6]
B = ['a', 'b', 'c', 'd', 'e', 'f']
O = [0, 2, 4, 6]
csr2 = CSR2(A, B, O)
assert csr2(0, 0) == (1, 'a')
assert csr2(1, 1) == (4, 'd')
assert csr2(2, 0) == (5, 'e')
# Float types
A_float = [1.1, 2.2, 3.3, 4.4]
B_float = [10.1, 20.2, 30.3, 40.4]
O_float = [0, 2, 4]
csr2_float = CSR2(A_float, B_float, O_float)
assert csr2_float(0, 0) == (1.1, 10.1)
assert csr2_float(1, 1) == (4.4, 40.4)
def test_bounds_checking(self):
"""Test that appropriate errors are raised for out-of-bounds access"""
A = [1, 2, 3, 4]
B = [10, 20, 30, 40]
O = [0, 2, 4] # 2 rows: [(1,10),(2,20)], [(3,30),(4,40)]
csr2 = CSR2(A, B, O)
# These should work
assert csr2(0, 1) == (2, 20)
assert csr2(1, 0) == (3, 30)
# Out of bounds row access should raise IndexError when accessing the view
row = csr2[0]
with pytest.raises(IndexError):
row[2] # Row 0 only has 2 elements (indices 0, 1)
def test_random_operations(self):
"""Test random operations for robustness"""
random.seed(42) # For reproducibility
# Create random CSR2 structure
num_rows = 50
total_elements = 500
A = [random.randint(1, 1000) for _ in range(total_elements)]
B = [random.randint(1000, 2000) for _ in range(total_elements)]
# Generate random row sizes
O = [0]
remaining = total_elements
for i in range(num_rows - 1):
if remaining > 0:
row_size = random.randint(0, min(20, remaining))
O.append(O[-1] + row_size)
remaining -= row_size
else:
O.append(O[-1])
O.append(total_elements)
csr2 = CSR2(A, B, O)
assert len(csr2) == num_rows
# Perform random operations
for _ in range(100):
row_idx = random.randint(0, num_rows - 1)
row = csr2[row_idx]
if len(row) > 0:
col_idx = random.randint(0, len(row) - 1)
# Read operation
val1 = csr2(row_idx, col_idx)
val2 = row[col_idx]
assert val1 == val2
# Write operation
new_val = (random.randint(2000, 3000), random.randint(3000, 4000))
csr2.set(row_idx, col_idx, new_val)
assert csr2(row_idx, col_idx) == new_val
assert row[col_idx] == new_val
def test_view_isolation(self):
"""Test that different views don't interfere with each other"""
A = [1, 2, 3, 4, 5, 6, 7, 8]
B = [10, 20, 30, 40, 50, 60, 70, 80]
O = [0, 3, 5, 8] # 3 rows: [(1,10),(2,20),(3,30)], [(4,40),(5,50)], [(6,60),(7,70),(8,80)]
csr2 = CSR2(A, B, O)
# Get multiple views
view0 = csr2[0]
view1 = csr2[1]
view2 = csr2[2]
# Modify through different views
view0[0] = (10, 100)
view1[1] = (50, 500)
view2[2] = (80, 800)
# Check that modifications are isolated and correct
assert A == [10, 2, 3, 4, 50, 6, 7, 80]
assert B == [100, 20, 30, 40, 500, 60, 70, 800]
assert view0[0] == (10, 100)
assert view1[1] == (50, 500)
assert view2[2] == (80, 800)
# Other elements should be unchanged
assert view0[1] == (2, 20)
assert view1[0] == (4, 40)
assert view2[0] == (6, 60)
def test_bucketize_order_preservation(self):
"""Test bucketize behavior with element ordering"""
N = 2
K = [0, 1, 0, 1, 0] # Alternating buckets
V = [1, 2, 3, 4, 5]
W = [10, 20, 30, 40, 50]
csr2 = CSR2.bucketize(N, K, V, W)
# Bucket 0 should contain elements from positions 0, 2, 4
# The bucketize algorithm processes in reverse order, so elements are inserted last-to-first
row0 = csr2[0]
assert len(row0) == 3
# Elements should be in reverse insertion order: (5,50), (3,30), (1,10)
elements_bucket0 = [row0[i] for i in range(len(row0))]
assert set(elements_bucket0) == {(1, 10), (3, 30), (5, 50)}
# Bucket 1 should contain elements from positions 1, 3
row1 = csr2[1]
assert len(row1) == 2
# Elements should be in reverse insertion order: (4,40), (2,20)
elements_bucket1 = [row1[i] for i in range(len(row1))]
assert set(elements_bucket1) == {(2, 20), (4, 40)}
def test_complex_operations_sequence(self):
"""Test complex sequence of operations using persistent views"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
O = [0, 3, 6, 9] # 3 rows of 3 elements each
csr2 = CSR2(A, B, O)
# Get views and perform operations
row0 = csr2[0]
row1 = csr2[1]
# Sort first row
row0.sort()
assert A[:3] == [1, 2, 3]
assert B[:3] == [10, 20, 30]
# Reverse second row
row1.reverse()
assert A[3:6] == [6, 5, 4]
assert B[3:6] == [60, 50, 40]
# Modify third row using set method
csr2.set(2, 0, (90, 900))
csr2.set(2, 1, (80, 800))
csr2.set(2, 2, (70, 700))
assert A[6:9] == [90, 80, 70]
assert B[6:9] == [900, 800, 700]
# Verify final state
assert csr2(0, 0) == (1, 10)
assert csr2(1, 0) == (6, 60)
assert csr2(2, 0) == (90, 900)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
from typing import Generic
from typing import TypeVar
_S = TypeVar('S')
_T = TypeVar('T')
_U = TypeVar('U')
def argsort_ranged(A: list[int], l: int, r: int, reverse=False):
P = Packer(r-l-1); I = [A[l+i] for i in range(r-l)]; P.ienumerate(I, reverse); I.sort()
for i in range(r-l): I[i] = (I[i] & P.m) + l
return I
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
def isort_ranged(*L: list, l: int, r: int, reverse=False):
n = r - l
order = argsort_ranged(L[0], l, r, reverse=reverse)
inv = [0] * n
# order contains indices in range [l, r), need to map to [0, n)
for i in range(n): inv[order[i]-l] = i
for i in range(n):
j = order[i] - l # j is in range [0, n)
for A in L: A[l+i], A[l+j] = A[l+j], A[l+i]
order[inv[i]], order[inv[j]] = order[inv[j]], order[inv[i]]
inv[i], inv[j] = inv[j], inv[i]
return L
class view2(Generic[_S, _T]):
__slots__ = 'A', 'B', 'l', 'r'
def __init__(V, A: list[_S], B: list[_T], l: int, r: int): V.A, V.B, V.l, V.r = A, B, 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], V.B[V.l+i]
else: raise IndexError
def __setitem__(V, i: int, v: tuple[_S, _T]): V.A[V.l+i], V.B[V.l+i] = v
def __contains__(V, v: tuple[_S, _T]): raise NotImplemented
def set_range(V, l: int, r: int): V.l, V.r = l, r
def index(V, v: tuple[_S, _T]): raise NotImplemented
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]; V.B[l], V.B[r] = V.B[r], V.B[l]; l += 1; r -= 1
def sort(V, reverse=False): isort_ranged(V.A, V.B, l=V.l, r=V.r, reverse=reverse)
def pop(V): V.r -= 1; return V.A[V.r], V.B[V.r]
def append(V, v: tuple[_S, _T]): V.A[V.r], V.B[V.r] = v; V.r += 1
def popleft(V): V.l += 1; return V.A[V.l-1], V.B[V.l-1]
def appendleft(V, v: tuple[_S, _T]): V.l -= 1; V.A[V.l], V.B[V.l] = v;
def validate(V): return 0 <= V.l <= V.r <= len(V.A)
class CSR2(Generic[_T]):
__slots__ = 'A', 'B', 'O'
def __init__(csr, A: list[_S], B: list[_T], O: list[int]): csr.A, csr.B, csr.O = A, B, O
def __len__(csr): return len(csr.O)-1
def __getitem__(csr, i: int): return view2(csr.A, csr.B, csr.O[i], csr.O[i+1])
def __call__(csr, i: int, j: int): ij = csr.O[i]+j; return csr.A[ij], csr.B[ij]
def set(csr, i: int, j: int, v: _T): ij = csr.O[i]+j; csr.A[ij], csr.B[ij] = v
@classmethod
def bucketize(cls, N: int, K: list[int], V: list[_T], W: list[_T]):
A: list[_S] = [0]*len(K); B: list[_T] = [0]*len(K); O = [0]*(N+1)
for k in K: O[k] += 1
for i in range(N): O[i+1] += O[i]
for e in range(len(K)): k = K[~e]; O[k] -= 1; A[O[k]] = V[~e]; B[O[k]] = W[~e]
return cls(A, B, O)
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
"""
import sys
from typing import Type, Union, overload
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
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)
@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)
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
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()