cp_library/alg/divcon/partition_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Required by

• cp_library/alg/divcon/qselect_fn.py
• cp_library/math/median_fn.py

Verified with

• test/atcoder/arc/arc122_b_insurance_median.test.py
• test/atcoder/arc/arc182_d_increment_decrement_again_qselect.test.py

Code

import cp_library.alg.divcon.__header__

def partition(A, l, r, p) -> int:
    '''Partition subarray [l,r)'''
    A[p], A[r], p = A[r := r-1], A[p], l
    for j in range(l, r):
        if A[j] <= A[r]: A[p], A[j], p = A[j], A[p], p+1
    A[p], A[r] = A[r], A[p]
    return p

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

def partition(A, l, r, p) -> int:
    '''Partition subarray [l,r)'''
    A[p], A[r], p = A[r := r-1], A[p], l
    for j in range(l, r):
        if A[j] <= A[r]: A[p], A[j], p = A[j], A[p], p+1
    A[p], A[r] = A[r], A[p]
    return p

Back to top page