東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）G,Ex問題メモ

def solve(n, aaa):
    n2 = (n + 1) // 2
    l = 0
    r = 1 << 30
    while l + 1 < r:
        m = (l + r) >> 1
        if calc1(aaa, m, 29) >= n2:
            l = m
        else:
            r = m
    return l


def calc1(aaa, m, d):
    if d == -1:
        return len(aaa) // 2
    if len(aaa) < 2:
        return 0
    bit = 1 << d
    aaa0 = []
    aaa1 = []
    for a in aaa:
        if a & bit:
            aaa1.append(a)
        else:
            aaa0.append(a)

    if m & bit:
        return calc2(aaa0, aaa1, m, d - 1)
    else:
        if len(aaa0) > len(aaa1):
            aaa0, aaa1 = aaa1, aaa0
        diff = len(aaa1) - len(aaa0)
        res = len(aaa0) + min(diff // 2, calc1(aaa1, m, d - 1))
        return res


def calc2(aaa0, aaa1, m, d):
    if d == -1:
        return min(len(aaa0), len(aaa1))
    if len(aaa0) == 0 or len(aaa1) == 0:
        return 0

    bit = 1 << d
    aaa00 = []
    aaa01 = []
    aaa10 = []
    aaa11 = []
    for a in aaa0:
        if a & bit:
            aaa01.append(a)
        else:
            aaa00.append(a)
    for a in aaa1:
        if a & bit:
            aaa11.append(a)
        else:
            aaa10.append(a)

    if m & bit:
        res1 = calc2(aaa01, aaa10, m, d - 1)
        res2 = calc2(aaa00, aaa11, m, d - 1)
        return res1 + res2
    else:
        res1 = min(len(aaa01), len(aaa10))
        res2 = min(len(aaa00), len(aaa11))
        res = res1 + res2

        if len(aaa01) > len(aaa10) and len(aaa11) > len(aaa00):
            limit = min(len(aaa01) - len(aaa10), len(aaa11) - len(aaa00))
            res += min(limit, calc2(aaa01, aaa11, m, d - 1))
        elif len(aaa01) < len(aaa10) and len(aaa11) < len(aaa00):
            limit = min(len(aaa10) - len(aaa01), len(aaa00) - len(aaa11))
            res += min(limit, calc2(aaa00, aaa10, m, d - 1))

        return res


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(ans)

import sys
from heapq import heapify, heappop, heappush

input = sys.stdin.buffer.readline


def encode(a, b):
    return (a << 20) | b


def decode(key):
    a = key >> 20
    b = key ^ (a << 20)
    return a, b


def solve(n, m, fwd_links, bwd_links, in_counts, out_counts, lll, rrr):
    r_limit = rrr.copy()
    q = [i for i, o in enumerate(out_counts) if o == 0]
    fixed = len(q)
    while q:
        v = q.pop()
        for u in bwd_links[v]:
            out_counts[u] -= 1
            r_limit[u] = min(r_limit[u], r_limit[v] - 1)
            if out_counts[u] == 0:
                q.append(u)
                fixed += 1

    if fixed < n:
        return False

    topo = []
    stock = [[] for _ in range(n + 2)]
    q = []

    for v, ic in enumerate(in_counts):
        if ic == 0:
            item = encode(r_limit[v], v)
            if lll[v] == 1:
                q.append(item)
            else:
                stock[lll[v]].append(item)

    heapify(q)
    while q:
        rl, u = decode(heappop(q))
        topo.append(u)
        if not (lll[u] <= len(topo) <= r_limit[u]):
            return False
        next_l = len(topo) + 1
        for v in fwd_links[u]:
            in_counts[v] -= 1
            if in_counts[v] == 0:
                item = encode(r_limit[v], v)
                if lll[v] <= next_l:
                    heappush(q, item)
                else:
                    stock[lll[v]].append(item)
        for item in stock[next_l]:
            heappush(q, item)

    if len(topo) < n:
        return False

    ans = [0] * n
    for i, t in enumerate(topo):
        ans[t] = i + 1

    return ans


n, m = map(int, input().split())
fwd_links = [set() for _ in range(n)]
bwd_links = [set() for _ in range(n)]
in_counts = [0] * n
out_counts = [0] * n

for _ in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    fwd_links[s].add(t)
    bwd_links[t].add(s)
    out_counts[s] += 1
    in_counts[t] += 1

lll = [0] * n
rrr = [0] * n
for i in range(n):
    l, r = map(int, input().split())
    lll[i] = l
    rrr[i] = r

ans = solve(n, m, fwd_links, bwd_links, in_counts, out_counts, lll, rrr)
if ans == False:
    print('No')
else:
    print('Yes')
    print(*ans)