cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unittests/ds/view/view2_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/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 TestView2:
def test_initialization(self):
"""Test basic initialization of view2"""
A = [1, 2, 3, 4, 5]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 1, 4)
assert v.A is A
assert v.B is B
assert v.l == 1
assert v.r == 4
assert len(v) == 3
def test_len(self):
"""Test __len__ method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
# Test different ranges
assert len(view2(A, B, 0, 5)) == 5
assert len(view2(A, B, 2, 7)) == 5
assert len(view2(A, B, 0, 10)) == 10
assert len(view2(A, B, 5, 5)) == 0 # Empty range
def test_getitem(self):
"""Test __getitem__ method"""
A = [10, 20, 30, 40, 50]
B = ['x', 'y', 'z', 'w', 'v']
v = view2(A, B, 1, 4) # View of [(20,'y'), (30,'z'), (40,'w')]
assert v[0] == (20, 'y')
assert v[1] == (30, 'z')
assert v[2] == (40, 'w')
# Test IndexError for out of bounds
with pytest.raises(IndexError):
v[3]
with pytest.raises(IndexError):
v[-1]
def test_setitem(self):
"""Test __setitem__ method"""
A = [10, 20, 30, 40, 50]
B = ['x', 'y', 'z', 'w', 'v']
v = view2(A, B, 1, 4) # View of [(20,'y'), (30,'z'), (40,'w')]
v[0] = (25, 'Y')
v[1] = (35, 'Z')
v[2] = (45, 'W')
assert A == [10, 25, 35, 45, 50]
assert B == ['x', 'Y', 'Z', 'W', 'v']
assert v[0] == (25, 'Y')
assert v[1] == (35, 'Z')
assert v[2] == (45, 'W')
def test_contains_not_implemented(self):
"""Test that __contains__ raises NotImplemented"""
A = [1, 2, 3, 4, 5]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 1, 4)
with pytest.raises(TypeError): # NotImplemented raises TypeError
(2, 'b') in v
def test_index_not_implemented(self):
"""Test that index raises NotImplemented"""
A = [1, 2, 3, 4, 5]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 1, 4)
with pytest.raises(TypeError): # NotImplemented raises TypeError
v.index((2, 'b'))
def test_set_range(self):
"""Test set_range method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
v = view2(A, B, 2, 5)
assert len(v) == 3
assert v[0] == (3, 30)
# Change the range
v.set_range(4, 8)
assert len(v) == 4
assert v[0] == (5, 50)
assert v[1] == (6, 60)
assert v[2] == (7, 70)
assert v[3] == (8, 80)
def test_reverse(self):
"""Test reverse method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
v = view2(A, B, 2, 7) # View of [(3,30), (4,40), (5,50), (6,60), (7,70)]
v.reverse()
# Check that the view is reversed
assert v[0] == (7, 70)
assert v[1] == (6, 60)
assert v[2] == (5, 50)
assert v[3] == (4, 40)
assert v[4] == (3, 30)
# Check that the underlying arrays are modified
assert A == [1, 2, 7, 6, 5, 4, 3, 8, 9]
assert B == [10, 20, 70, 60, 50, 40, 30, 80, 90]
def test_sort(self):
"""Test sort method"""
A = [1, 5, 2, 8, 3, 9, 4, 6, 7]
B = [10, 50, 20, 80, 30, 90, 40, 60, 70]
v = view2(A, B, 2, 7) # View of [(2,20), (8,80), (3,30), (9,90), (4,40)]
v.sort()
# Check that the view is sorted by A values
assert v[0] == (2, 20)
assert v[1] == (3, 30)
assert v[2] == (4, 40)
assert v[3] == (8, 80)
assert v[4] == (9, 90)
# Check that the underlying arrays are modified correctly
assert A == [1, 5, 2, 3, 4, 8, 9, 6, 7]
assert B == [10, 50, 20, 30, 40, 80, 90, 60, 70]
def test_sort_reverse(self):
"""Test sort method with reverse=True"""
A = [1, 5, 2, 8, 3, 9, 4, 6, 7]
B = [10, 50, 20, 80, 30, 90, 40, 60, 70]
v = view2(A, B, 2, 7) # View of [(2,20), (8,80), (3,30), (9,90), (4,40)]
v.sort(reverse=True)
# Check that the view is sorted in reverse by A values
assert v[0] == (9, 90)
assert v[1] == (8, 80)
assert v[2] == (4, 40)
assert v[3] == (3, 30)
assert v[4] == (2, 20)
# Check that the underlying arrays are modified correctly
assert A == [1, 5, 9, 8, 4, 3, 2, 6, 7]
assert B == [10, 50, 90, 80, 40, 30, 20, 60, 70]
def test_pop(self):
"""Test pop method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
v = view2(A, B, 2, 6) # View of [(3,30), (4,40), (5,50), (6,60)]
assert len(v) == 4
# Pop from the end
popped = v.pop()
assert popped == (6, 60)
assert len(v) == 3
assert v[2] == (5, 50) # Last element is now (5,50)
# Pop again
popped = v.pop()
assert popped == (5, 50)
assert len(v) == 2
def test_append(self):
"""Test append method"""
A = [1, 2, 3, 4, 5, 0, 0, 0, 9] # Extra space for appending
B = [10, 20, 30, 40, 50, 0, 0, 0, 90]
v = view2(A, B, 2, 5) # View of [(3,30), (4,40), (5,50)]
assert len(v) == 3
# Append to the end
v.append((6, 60))
assert len(v) == 4
assert v[3] == (6, 60)
assert A[5] == 6 # Check underlying arrays
assert B[5] == 60
# Append again
v.append((7, 70))
assert len(v) == 5
assert v[4] == (7, 70)
def test_popleft(self):
"""Test popleft method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
v = view2(A, B, 2, 6) # View of [(3,30), (4,40), (5,50), (6,60)]
assert len(v) == 4
# Pop from the beginning
popped = v.popleft()
assert popped == (3, 30)
assert len(v) == 3
assert v[0] == (4, 40) # First element is now (4,40)
# Pop again
popped = v.popleft()
assert popped == (4, 40)
assert len(v) == 2
assert v[0] == (5, 50)
def test_appendleft(self):
"""Test appendleft method"""
A = [0, 0, 1, 2, 3, 4, 5, 6, 7] # Extra space at beginning
B = [0, 0, 10, 20, 30, 40, 50, 60, 70]
v = view2(A, B, 4, 7) # View of [(3,30), (4,40), (5,50)]
assert len(v) == 3
assert v[0] == (3, 30)
# Append to the beginning
v.appendleft((2, 20))
assert len(v) == 4
assert v[0] == (2, 20)
assert v[1] == (3, 30)
assert A[3] == 2 # Check underlying arrays
assert B[3] == 20
# Append again
v.appendleft((1, 10))
assert len(v) == 5
assert v[0] == (1, 10)
assert v[1] == (2, 20)
def test_validate(self):
"""Test validate method"""
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50]
# Valid ranges
v1 = view2(A, B, 0, 5)
assert v1.validate() == True
v2 = view2(A, B, 2, 4)
assert v2.validate() == True
v3 = view2(A, B, 3, 3) # Empty range
assert v3.validate() == True
# Invalid ranges
v4 = view2(A, B, -1, 3)
assert v4.validate() == False
v5 = view2(A, B, 2, 6) # r > len(A)
assert v5.validate() == False
v6 = view2(A, B, 3, 2) # l > r
assert v6.validate() == False
def test_empty_view(self):
"""Test operations on empty view"""
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50]
v = view2(A, B, 3, 3) # Empty view
assert len(v) == 0
# Test that operations on empty view behave correctly
with pytest.raises(IndexError):
v[0]
def test_edge_cases(self):
"""Test edge cases"""
# Single element view
A = [10, 20, 30, 40, 50]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 2, 3) # View of [(30, 'c')]
assert len(v) == 1
assert v[0] == (30, 'c')
# Modify single element
v[0] = (35, 'C')
assert A == [10, 20, 35, 40, 50]
assert B == ['a', 'b', 'C', 'd', 'e']
def test_view_operations_sequence(self):
"""Test a sequence of operations"""
A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
v = view2(A, B, 2, 8) # View of [(30,3), (40,4), (50,5), (60,6), (70,7), (80,8)]
# Initial state
assert len(v) == 6
assert v[0] == (30, 3)
assert v[5] == (80, 8)
# Modify some elements
v[1] = (45, 14)
v[3] = (65, 16)
assert A[3] == 45
assert B[3] == 14
assert A[5] == 65
assert B[5] == 16
# Pop and append
popped = v.pop()
assert popped == (80, 8)
assert len(v) == 5
v.append((85, 18))
assert len(v) == 6
assert v[5] == (85, 18)
# Reverse
v.reverse()
assert v[0] == (85, 18)
assert v[5] == (30, 3)
def test_with_different_types(self):
"""Test view2 with different data types"""
# Mixed types
A = [1, 2, 3, 4, 5, 6]
B = [1.1, 2.2, 3.3, 4.4, 5.5, 6.6]
v = view2(A, B, 1, 4) # [(2, 2.2), (3, 3.3), (4, 4.4)]
assert len(v) == 3
assert v[0] == (2, 2.2)
assert v[1] == (3, 3.3)
assert v[2] == (4, 4.4)
v.sort()
assert v[0] == (2, 2.2)
assert v[1] == (3, 3.3)
assert v[2] == (4, 4.4)
# Integer pairs (since the sort function requires integer keys)
A = [5, 2, 4, 1, 3]
B = [50, 20, 40, 10, 30]
v = view2(A, B, 1, 4) # [(2, 20), (4, 40), (1, 10)]
assert len(v) == 3
assert v[1] == (4, 40)
v.sort() # Should sort by A values
assert v[0] == (1, 10)
assert v[1] == (2, 20)
assert v[2] == (4, 40)
def test_large_data_operations(self):
"""Test operations on larger datasets"""
# Create large dataset
A = list(range(1000))
B = list(range(1000, 2000))
v = view2(A, B, 100, 900) # 800 elements
assert len(v) == 800
assert v[0] == (100, 1100)
assert v[799] == (899, 1899)
# Test modification
v[100] = (9999, 8888)
assert A[200] == 9999
assert B[200] == 8888
def test_random_operations(self):
"""Test random operations for robustness"""
random.seed(42) # For reproducibility
# Create test data
A = list(range(100))
B = list(range(100, 200))
original_A = A.copy()
original_B = B.copy()
# Create view
start, end = 20, 80
v = view2(A, B, start, end)
# Perform random operations
for _ in range(50):
op = random.choice(['read', 'write'])
if op == 'read' and len(v) > 0:
idx = random.randint(0, len(v) - 1)
val_a, val_b = v[idx]
assert val_a == A[start + idx]
assert val_b == B[start + idx]
elif op == 'write' and len(v) > 0:
idx = random.randint(0, len(v) - 1)
new_val_a = random.randint(1000, 2000)
new_val_b = random.randint(2000, 3000)
v[idx] = (new_val_a, new_val_b)
assert A[start + idx] == new_val_a
assert B[start + idx] == new_val_b
def test_view_modification_boundary_safety(self):
"""Test that view modifications don't affect data outside the view"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B = [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
original_A = A.copy()
original_B = B.copy()
v = view2(A, B, 3, 7) # View of [(4,14), (5,15), (6,16), (7,17)]
# Modify view
v[0] = (40, 140)
v[1] = (50, 150)
v[2] = (60, 160)
v[3] = (70, 170)
# Check that only the view range was modified
assert A[0:3] == original_A[0:3] # Before view unchanged
assert A[7:] == original_A[7:] # After view unchanged
assert B[0:3] == original_B[0:3] # Before view unchanged
assert B[7:] == original_B[7:] # After view unchanged
assert A[3:7] == [40, 50, 60, 70] # View range changed
assert B[3:7] == [140, 150, 160, 170] # View range changed
def test_mismatched_array_lengths(self):
"""Test behavior with mismatched array lengths"""
# Arrays of different lengths should still work within valid ranges
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50, 60, 70] # Longer than A
# View that fits within both arrays
v = view2(A, B, 1, 4)
assert len(v) == 3
assert v[0] == (2, 20)
assert v[2] == (4, 40)
# Validation should check against A (assuming it's the limiting factor)
v_invalid = view2(A, B, 0, 6) # Beyond A's length
assert v_invalid.validate() == False
def test_sort_stability(self):
"""Test sort stability with duplicate keys"""
A = [3, 1, 3, 2, 3, 1, 2]
B = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
v = view2(A, B, 0, 7)
v.sort()
# Check that sorting worked correctly
expected_A = [1, 1, 2, 2, 3, 3, 3]
assert A == expected_A
# Check that B values were rearranged along with A
for i in range(len(v)):
a_val, b_val = v[i]
assert a_val == expected_A[i]
from cp_library.ds.view.view2_cls import view2
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 TestView2:
def test_initialization(self):
"""Test basic initialization of view2"""
A = [1, 2, 3, 4, 5]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 1, 4)
assert v.A is A
assert v.B is B
assert v.l == 1
assert v.r == 4
assert len(v) == 3
def test_len(self):
"""Test __len__ method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
# Test different ranges
assert len(view2(A, B, 0, 5)) == 5
assert len(view2(A, B, 2, 7)) == 5
assert len(view2(A, B, 0, 10)) == 10
assert len(view2(A, B, 5, 5)) == 0 # Empty range
def test_getitem(self):
"""Test __getitem__ method"""
A = [10, 20, 30, 40, 50]
B = ['x', 'y', 'z', 'w', 'v']
v = view2(A, B, 1, 4) # View of [(20,'y'), (30,'z'), (40,'w')]
assert v[0] == (20, 'y')
assert v[1] == (30, 'z')
assert v[2] == (40, 'w')
# Test IndexError for out of bounds
with pytest.raises(IndexError):
v[3]
with pytest.raises(IndexError):
v[-1]
def test_setitem(self):
"""Test __setitem__ method"""
A = [10, 20, 30, 40, 50]
B = ['x', 'y', 'z', 'w', 'v']
v = view2(A, B, 1, 4) # View of [(20,'y'), (30,'z'), (40,'w')]
v[0] = (25, 'Y')
v[1] = (35, 'Z')
v[2] = (45, 'W')
assert A == [10, 25, 35, 45, 50]
assert B == ['x', 'Y', 'Z', 'W', 'v']
assert v[0] == (25, 'Y')
assert v[1] == (35, 'Z')
assert v[2] == (45, 'W')
def test_contains_not_implemented(self):
"""Test that __contains__ raises NotImplemented"""
A = [1, 2, 3, 4, 5]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 1, 4)
with pytest.raises(TypeError): # NotImplemented raises TypeError
(2, 'b') in v
def test_index_not_implemented(self):
"""Test that index raises NotImplemented"""
A = [1, 2, 3, 4, 5]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 1, 4)
with pytest.raises(TypeError): # NotImplemented raises TypeError
v.index((2, 'b'))
def test_set_range(self):
"""Test set_range method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
v = view2(A, B, 2, 5)
assert len(v) == 3
assert v[0] == (3, 30)
# Change the range
v.set_range(4, 8)
assert len(v) == 4
assert v[0] == (5, 50)
assert v[1] == (6, 60)
assert v[2] == (7, 70)
assert v[3] == (8, 80)
def test_reverse(self):
"""Test reverse method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
v = view2(A, B, 2, 7) # View of [(3,30), (4,40), (5,50), (6,60), (7,70)]
v.reverse()
# Check that the view is reversed
assert v[0] == (7, 70)
assert v[1] == (6, 60)
assert v[2] == (5, 50)
assert v[3] == (4, 40)
assert v[4] == (3, 30)
# Check that the underlying arrays are modified
assert A == [1, 2, 7, 6, 5, 4, 3, 8, 9]
assert B == [10, 20, 70, 60, 50, 40, 30, 80, 90]
def test_sort(self):
"""Test sort method"""
A = [1, 5, 2, 8, 3, 9, 4, 6, 7]
B = [10, 50, 20, 80, 30, 90, 40, 60, 70]
v = view2(A, B, 2, 7) # View of [(2,20), (8,80), (3,30), (9,90), (4,40)]
v.sort()
# Check that the view is sorted by A values
assert v[0] == (2, 20)
assert v[1] == (3, 30)
assert v[2] == (4, 40)
assert v[3] == (8, 80)
assert v[4] == (9, 90)
# Check that the underlying arrays are modified correctly
assert A == [1, 5, 2, 3, 4, 8, 9, 6, 7]
assert B == [10, 50, 20, 30, 40, 80, 90, 60, 70]
def test_sort_reverse(self):
"""Test sort method with reverse=True"""
A = [1, 5, 2, 8, 3, 9, 4, 6, 7]
B = [10, 50, 20, 80, 30, 90, 40, 60, 70]
v = view2(A, B, 2, 7) # View of [(2,20), (8,80), (3,30), (9,90), (4,40)]
v.sort(reverse=True)
# Check that the view is sorted in reverse by A values
assert v[0] == (9, 90)
assert v[1] == (8, 80)
assert v[2] == (4, 40)
assert v[3] == (3, 30)
assert v[4] == (2, 20)
# Check that the underlying arrays are modified correctly
assert A == [1, 5, 9, 8, 4, 3, 2, 6, 7]
assert B == [10, 50, 90, 80, 40, 30, 20, 60, 70]
def test_pop(self):
"""Test pop method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
v = view2(A, B, 2, 6) # View of [(3,30), (4,40), (5,50), (6,60)]
assert len(v) == 4
# Pop from the end
popped = v.pop()
assert popped == (6, 60)
assert len(v) == 3
assert v[2] == (5, 50) # Last element is now (5,50)
# Pop again
popped = v.pop()
assert popped == (5, 50)
assert len(v) == 2
def test_append(self):
"""Test append method"""
A = [1, 2, 3, 4, 5, 0, 0, 0, 9] # Extra space for appending
B = [10, 20, 30, 40, 50, 0, 0, 0, 90]
v = view2(A, B, 2, 5) # View of [(3,30), (4,40), (5,50)]
assert len(v) == 3
# Append to the end
v.append((6, 60))
assert len(v) == 4
assert v[3] == (6, 60)
assert A[5] == 6 # Check underlying arrays
assert B[5] == 60
# Append again
v.append((7, 70))
assert len(v) == 5
assert v[4] == (7, 70)
def test_popleft(self):
"""Test popleft method"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
B = [10, 20, 30, 40, 50, 60, 70, 80, 90]
v = view2(A, B, 2, 6) # View of [(3,30), (4,40), (5,50), (6,60)]
assert len(v) == 4
# Pop from the beginning
popped = v.popleft()
assert popped == (3, 30)
assert len(v) == 3
assert v[0] == (4, 40) # First element is now (4,40)
# Pop again
popped = v.popleft()
assert popped == (4, 40)
assert len(v) == 2
assert v[0] == (5, 50)
def test_appendleft(self):
"""Test appendleft method"""
A = [0, 0, 1, 2, 3, 4, 5, 6, 7] # Extra space at beginning
B = [0, 0, 10, 20, 30, 40, 50, 60, 70]
v = view2(A, B, 4, 7) # View of [(3,30), (4,40), (5,50)]
assert len(v) == 3
assert v[0] == (3, 30)
# Append to the beginning
v.appendleft((2, 20))
assert len(v) == 4
assert v[0] == (2, 20)
assert v[1] == (3, 30)
assert A[3] == 2 # Check underlying arrays
assert B[3] == 20
# Append again
v.appendleft((1, 10))
assert len(v) == 5
assert v[0] == (1, 10)
assert v[1] == (2, 20)
def test_validate(self):
"""Test validate method"""
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50]
# Valid ranges
v1 = view2(A, B, 0, 5)
assert v1.validate() == True
v2 = view2(A, B, 2, 4)
assert v2.validate() == True
v3 = view2(A, B, 3, 3) # Empty range
assert v3.validate() == True
# Invalid ranges
v4 = view2(A, B, -1, 3)
assert v4.validate() == False
v5 = view2(A, B, 2, 6) # r > len(A)
assert v5.validate() == False
v6 = view2(A, B, 3, 2) # l > r
assert v6.validate() == False
def test_empty_view(self):
"""Test operations on empty view"""
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50]
v = view2(A, B, 3, 3) # Empty view
assert len(v) == 0
# Test that operations on empty view behave correctly
with pytest.raises(IndexError):
v[0]
def test_edge_cases(self):
"""Test edge cases"""
# Single element view
A = [10, 20, 30, 40, 50]
B = ['a', 'b', 'c', 'd', 'e']
v = view2(A, B, 2, 3) # View of [(30, 'c')]
assert len(v) == 1
assert v[0] == (30, 'c')
# Modify single element
v[0] = (35, 'C')
assert A == [10, 20, 35, 40, 50]
assert B == ['a', 'b', 'C', 'd', 'e']
def test_view_operations_sequence(self):
"""Test a sequence of operations"""
A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
B = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
v = view2(A, B, 2, 8) # View of [(30,3), (40,4), (50,5), (60,6), (70,7), (80,8)]
# Initial state
assert len(v) == 6
assert v[0] == (30, 3)
assert v[5] == (80, 8)
# Modify some elements
v[1] = (45, 14)
v[3] = (65, 16)
assert A[3] == 45
assert B[3] == 14
assert A[5] == 65
assert B[5] == 16
# Pop and append
popped = v.pop()
assert popped == (80, 8)
assert len(v) == 5
v.append((85, 18))
assert len(v) == 6
assert v[5] == (85, 18)
# Reverse
v.reverse()
assert v[0] == (85, 18)
assert v[5] == (30, 3)
def test_with_different_types(self):
"""Test view2 with different data types"""
# Mixed types
A = [1, 2, 3, 4, 5, 6]
B = [1.1, 2.2, 3.3, 4.4, 5.5, 6.6]
v = view2(A, B, 1, 4) # [(2, 2.2), (3, 3.3), (4, 4.4)]
assert len(v) == 3
assert v[0] == (2, 2.2)
assert v[1] == (3, 3.3)
assert v[2] == (4, 4.4)
v.sort()
assert v[0] == (2, 2.2)
assert v[1] == (3, 3.3)
assert v[2] == (4, 4.4)
# Integer pairs (since the sort function requires integer keys)
A = [5, 2, 4, 1, 3]
B = [50, 20, 40, 10, 30]
v = view2(A, B, 1, 4) # [(2, 20), (4, 40), (1, 10)]
assert len(v) == 3
assert v[1] == (4, 40)
v.sort() # Should sort by A values
assert v[0] == (1, 10)
assert v[1] == (2, 20)
assert v[2] == (4, 40)
def test_large_data_operations(self):
"""Test operations on larger datasets"""
# Create large dataset
A = list(range(1000))
B = list(range(1000, 2000))
v = view2(A, B, 100, 900) # 800 elements
assert len(v) == 800
assert v[0] == (100, 1100)
assert v[799] == (899, 1899)
# Test modification
v[100] = (9999, 8888)
assert A[200] == 9999
assert B[200] == 8888
def test_random_operations(self):
"""Test random operations for robustness"""
random.seed(42) # For reproducibility
# Create test data
A = list(range(100))
B = list(range(100, 200))
original_A = A.copy()
original_B = B.copy()
# Create view
start, end = 20, 80
v = view2(A, B, start, end)
# Perform random operations
for _ in range(50):
op = random.choice(['read', 'write'])
if op == 'read' and len(v) > 0:
idx = random.randint(0, len(v) - 1)
val_a, val_b = v[idx]
assert val_a == A[start + idx]
assert val_b == B[start + idx]
elif op == 'write' and len(v) > 0:
idx = random.randint(0, len(v) - 1)
new_val_a = random.randint(1000, 2000)
new_val_b = random.randint(2000, 3000)
v[idx] = (new_val_a, new_val_b)
assert A[start + idx] == new_val_a
assert B[start + idx] == new_val_b
def test_view_modification_boundary_safety(self):
"""Test that view modifications don't affect data outside the view"""
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
B = [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
original_A = A.copy()
original_B = B.copy()
v = view2(A, B, 3, 7) # View of [(4,14), (5,15), (6,16), (7,17)]
# Modify view
v[0] = (40, 140)
v[1] = (50, 150)
v[2] = (60, 160)
v[3] = (70, 170)
# Check that only the view range was modified
assert A[0:3] == original_A[0:3] # Before view unchanged
assert A[7:] == original_A[7:] # After view unchanged
assert B[0:3] == original_B[0:3] # Before view unchanged
assert B[7:] == original_B[7:] # After view unchanged
assert A[3:7] == [40, 50, 60, 70] # View range changed
assert B[3:7] == [140, 150, 160, 170] # View range changed
def test_mismatched_array_lengths(self):
"""Test behavior with mismatched array lengths"""
# Arrays of different lengths should still work within valid ranges
A = [1, 2, 3, 4, 5]
B = [10, 20, 30, 40, 50, 60, 70] # Longer than A
# View that fits within both arrays
v = view2(A, B, 1, 4)
assert len(v) == 3
assert v[0] == (2, 20)
assert v[2] == (4, 40)
# Validation should check against A (assuming it's the limiting factor)
v_invalid = view2(A, B, 0, 6) # Beyond A's length
assert v_invalid.validate() == False
def test_sort_stability(self):
"""Test sort stability with duplicate keys"""
A = [3, 1, 3, 2, 3, 1, 2]
B = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
v = view2(A, B, 0, 7)
v.sort()
# Check that sorting worked correctly
expected_A = [1, 1, 2, 2, 3, 3, 3]
assert A == expected_A
# Check that B values were rearranged along with A
for i in range(len(v)):
a_val, b_val = v[i]
assert a_val == expected_A[i]
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
https://kobejean.github.io/cp-library
'''
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
from typing import Generic
from typing import TypeVar
_S = TypeVar('S')
_T = TypeVar('T')
_U = TypeVar('U')
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)
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()