cp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: cp_library/alg/iter/rank/rank_fn.py

Depends on

Required by

Verified with

Code

import cp_library.__header__
import cp_library.alg.__header__
import cp_library.alg.iter.__header__
import cp_library.alg.iter.rank.__header__
from cp_library.alg.iter.rank.irank_fn import irank

def rank(A: list[int], distinct = False): return (R := A.copy()), irank(R, distinct)
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''




def irank(A: list[int], distinct = False):
    P = Packer(len(A)-1); V = P.enumerate(A); V.sort()
    if distinct:
        for r, ai in enumerate(V): a, i = P.dec(ai); A[i], V[r] = r, a
    elif V:
        r, p = -1, V[-1]+1 # set p to unique value to trigger `if a != p` on first elm
        for ai in V:
            a, i = P.dec(ai)
            if a!=p: V[r:=r+1] = p = a
            A[i] = r
        del V[r+1:]
    return V



class Packer:
    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:=A.copy(), 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:=A.copy()); return A
    def iindices(P, A):
        for i,a in enumerate(A): A[i] = P.m&a

def rank(A: list[int], distinct = False): return (R := A.copy()), irank(R, distinct)
Back to top page