cp-library

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

View the Project on GitHub kobejean/cp-library

:heavy_check_mark: test/atcoder/arc/arc182_d_increment_decrement_again_qselect.test.py

Depends on

Code

# verification-helper: PROBLEM https://atcoder.jp/contests/arc182/tasks/arc182_d

def main():
    N, M = read()
    A = read()
    B = read()

    if M == 2:
        write(0 if A == B else -1)
        exit()

    def rel(x,y):
        return max(-1,min(x-y,1))

    C = [B[0]]

    for i in range(1,N):
        c = C[-1] - C[-1]%M + B[i]
        for Ci in range(c-M,c+2*M,M):
            if rel(A[i-1],A[i]) == rel(C[-1],Ci) and abs(C[-1]-Ci)<M:
                C.append(Ci)
                break
    median = qselect([c-a for a,c in zip(A,C)], N//2)
    ans = inf
    for i in range(median//M,median//M+2):
        now=0
        for j in range(N):
            now+=abs(A[j]+i*M-C[j])
        ans=min(ans,now)
    write(ans)

from math import inf
from cp_library.alg.divcon.qselect_fn import qselect
from cp_library.io.read_int_fn import read
from cp_library.io.write_fn import write
    
if __name__ == '__main__':
    main()
# verification-helper: PROBLEM https://atcoder.jp/contests/arc182/tasks/arc182_d

def main():
    N, M = read()
    A = read()
    B = read()

    if M == 2:
        write(0 if A == B else -1)
        exit()

    def rel(x,y):
        return max(-1,min(x-y,1))

    C = [B[0]]

    for i in range(1,N):
        c = C[-1] - C[-1]%M + B[i]
        for Ci in range(c-M,c+2*M,M):
            if rel(A[i-1],A[i]) == rel(C[-1],Ci) and abs(C[-1]-Ci)<M:
                C.append(Ci)
                break
    median = qselect([c-a for a,c in zip(A,C)], N//2)
    ans = inf
    for i in range(median//M,median//M+2):
        now=0
        for j in range(N):
            now+=abs(A[j]+i*M-C[j])
        ans=min(ans,now)
    write(ans)

from math import inf
'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from random import randint

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

def qselect(A, k, l=0, r=None):
    '''Find kth element in subarray [l,r)'''
    if r is None: r = len(A)
    while l != r-1:
        if k < (p := partition(A, l, r, randint(l,r-1))): r = p
        elif k > p: l = p+1
        else: return A[k]
    return A[k]


def read(shift=0, base=10):
    return [int(s, base) + shift for s in input().split()]
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")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)

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()
    
if __name__ == '__main__':
    main()
Back to top page