京东 2026-8-22 笔试真题 - 算法岗

import json
import math
import sys

import numpy as np


ALPHA = 0.2


def solve():
    data = json.loads(sys.stdin.buffer.readline())
    cal_y = np.asarray(data["cal_y"], dtype=np.int64)
    cal_p1 = np.asarray(data["cal_p1"], dtype=np.float64)
    test_p1 = np.asarray(data["test_p1"], dtype=np.float64)

    scores = np.where(cal_y == 1, 1.0 - cal_p1, cal_p1)
    scores.sort()

    n = scores.size
    k = math.ceil((n + 1) * (1.0 - ALPHA)) - 1
    if k >= n:
        k = n - 1
    q = scores[k]

    take0 = test_p1 <= q
    take1 = test_p1 >= 1.0 - q

    result = np.where(
        take0 & take1,
        -1,
        np.where(take1, 1, np.where(take0, 0, -2)),
    )
    print(json.dumps(result.tolist(), separators=(",", ":")))


if __name__ == "__main__":
    solve()

import sys
from heapq import heappop, heappush


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)
    n = next(iterator)
    t = next(iterator)
    positions = [next(iterator) for _ in range(n)]
    queries = [(next(iterator) - 1, next(iterator)) for _ in range(t)]

    coords = sorted(set(positions) | {value for _, value in queries})
    size = len(coords)
    rank = {value: index for index, value in enumerate(coords)}

    count = [0] * size
    bit = [0] * (size + 1)
    total = 0

    def bit_add(index, delta):
        nonlocal total
        total += delta
        index += 1
        while index <= size:
            bit[index] += delta
            index += index & -index

    def bit_sum(index):
        result = 0
        index += 1
        while index > 0:
            result += bit[index]
            index -= index & -index
        return result

    def bit_kth(k):
        """返回第 k 个锚点所在的零基压缩坐标，k 从 1 开始。"""
        index = 0
        step = 1 << (size.bit_length() - 1)
        while step:
            nxt = index + step
            if nxt <= size and bit[nxt] < k:
                index = nxt
                k -= bit[nxt]
            step >>= 1
        return index

    def neighbors(index):
        """仅在 count[index] == 0 时调用。"""
        left_count = bit_sum(index)
        left = bit_kth(left_count) if left_count > 0 else -1
        right = bit_kth(left_count + 1) if left_count < total else -1
        return left, right

    gap_count = {}
    max_heap = []

    def gap_add(gap):
        gap_count[gap] = gap_count.get(gap, 0) + 1
        heappush(max_heap, -gap)

    def gap_remove(gap):
        gap_count[gap] -= 1

    def largest_gap():
        while max_heap and gap_count.get(-max_heap[0], 0) == 0:
            heappop(max_heap)
        return -max_heap[0] if max_heap else 0

    distinct = 0

    def remove_at(index):
        nonlocal distinct
        count[index] -= 1
        bit_add(index, -1)
        if count[index] > 0:
            return

        distinct -= 1
        left, right = neighbors(index)
        if left >= 0 and right >= 0:
            gap_remove(coords[index] - coords[left])
            gap_remove(coords[right] - coords[index])
            gap_add(coords[right] - coords[left])
        elif left >= 0:
            gap_remove(coords[index] - coords[left])
        elif right >= 0:
            gap_remove(coords[right] - coords[index])

    def insert_at(index):
        nonlocal distinct
        if count[index] == 0:
            left, right = neighbors(index)
            if left >= 0 and right >= 0:
                gap_remove(coords[right] - coords[left])
                gap_add(coords[index] - coords[left])
                gap_add(coords[right] - coords[index])
            elif left >= 0:
                gap_add(coords[index] - coords[left])
            elif right >= 0:
                gap_add(coords[right] - coords[index])
            distinct += 1

        count[index] += 1
        bit_add(index, 1)

    for value in positions:
        index = rank[value]
        if count[index] == 0:
            distinct += 1
        count[index] += 1
        bit_add(index, 1)

    active = [index for index in range(size) if count[index] > 0]
    for left, right in zip(active, active[1:]):
        gap_add(coords[right] - coords[left])

    answers = []
    for item_index, new_value in queries:
        remove_at(rank[positions[item_index]])
        positions[item_index] = new_value
        insert_at(rank[new_value])
        answers.append(str(0 if distinct <= 1 else largest_gap() // 2))

    sys.stdout.write("\n".join(answers))


if __name__ == "__main__":
    solve()