java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n + 1];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        a[n] = -1;
        
        ArrayList<Integer>[] graph = new ArrayList[n * 4 + 4];
        for (int i = 0; i < graph.length; i++) graph[i] = new ArrayList<>();
        int[] id = new int[n + 1];
        id[n] = -1;
        
        int[] rev = new int[n * 4 + 4];
        build(graph, id, 1, 0, n - 1);
        
        Arrays.fill(rev, n);
        for (int i = 0; i < n; i++) rev[id[i]] = i;
        
        for (int i = 0; i < n; i++) {
            if (a[i] == -1) continue;
            
            int d = (a[i] % n + n) % n;
            if (d <= i) {
                if (d < i) update(graph, id, 1, 0, n - 1, d, i - 1, i);
            } else {
                update(graph, id, 1, 0, n - 1, d, n - 1, i);
                if (i > 0) update(graph, id, 1, 0, n - 1, 0, i - 1, i);
            }
        }
        
        int[] deg = new int[n * 4 + 4];
        PriorityQueue<int[]> queue = new PriorityQueue<>((int[] x, int[] y) -> x[0] - y[0]);
        for (int i = 0; i < n * 4 + 4; i++) {
            for (int v : graph[i]) deg[v]++;
        }
        for (int i = 0; i < n * 4 + 4; i++) {
            if (deg[i] == 0) queue.offer(new int[]{a[rev[i]], i});
        }
        
        ArrayList<Integer> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int val = cur[0];
            int node = cur[1];
            if (id[rev[node]] == node) ans.add(val);
            for (int v : graph[node]) {
                if (--deg[v] == 0) {
                    queue.offer(new int[]{a[rev[v]], v});
                }
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            if (ans.get(i)==-1)
                continue;
            System.out.print(ans.get(i));
            if (i + 1 == ans.size()) {
                System.out.println();
            } else {
                System.out.print(' ');
            }
        }
    }
    
    static void build(ArrayList<Integer>[] graph, int[] id, int x, int l, int r) {
        if (l == r) {
            id[l] = x;
            return;
        }
        int mid = l + (r - l) / 2;
        build(graph, id, x * 2, l, mid);
        build(graph, id, x * 2 + 1, mid + 1, r);
        graph[x * 2].add(x);
        graph[x * 2 + 1].add(x);
    }
    
    static void update(ArrayList<Integer>[] graph, int[] id, int x, int l, int r, int s, int t, int u) {
        if (s <= l && r <= t) {
            graph[x].add(id[u]);
            return;
        }
        int mid = l + (r - l) / 2;
        if (s <= mid) update(graph, id, x * 2, l, mid, s, t, u);
        if (t > mid) update(graph, id, x * 2 + 1, mid + 1, r, s, t, u);
    }
}

python

import heapq
from collections import defaultdict

def build(graph, id, x, l, r):
    if l == r:
        id[l] = x
        return
    mid = l + (r - l) // 2
    build(graph, id, x * 2, l, mid)
    build(graph, id, x * 2 + 1, mid + 1, r)
    graph[x * 2].append(x)
    graph[x * 2 + 1].append(x)

def update(graph, id, x, l, r, s, t, u):
    if s <= l and r <= t:
        graph[x].append(id[u])
        return
    mid = l + (r - l) // 2
    if s <= mid:
        update(graph, id, x * 2, l, mid, s, t, u)
    if t > mid:
        update(graph, id, x * 2 + 1, mid + 1, r, s, t, u)

def main():
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    a.append(-1)

    graph = defaultdict(list)
    id = [-1] * (n + 1)
    rev = [n] * (n * 4 + 4)

    build(graph, id, 1, 0, n - 1)

    for i in range(n):
        rev[id[i]] = i

    for i in range(n):
        if a[i] == -1:
            continue

        d = (a[i] % n + n) % n
        if d <= i:
            if d < i:
                update(graph, id, 1, 0, n - 1, d, i - 1, i)
        else:
            update(graph, id, 1, 0, n - 1, d, n - 1, i)
            if i > 0:
                update(graph, id, 1, 0, n - 1, 0, i - 1, i)

    deg = [0] * (n * 4 + 4)
    queue = []

    for i in range(n * 4 + 4):
        for v in graph[i]:
            deg[v] += 1

    for i in range(n * 4 + 4):
        if deg[i] == 0:
            heapq.heappush(queue, (a[rev[i]], i))

    ans = []
    while queue:
        val, node = heapq.heappop(queue)
        if id[rev[node]] == node:
            ans.append(val)
        for v in graph[node]:
            deg[v] -= 1
            if deg[v] == 0:
                heapq.heappush(queue, (a[rev[v]], v))

    for i in range(len(ans)):
        if ans[i] == -1:
            continue
        if i + 1 == len(ans):
            print(ans[i])
        else:
            print(ans[i], end=' ')

if __name__ == "__main__":
    main()

题目描述

在一个简单的哈希表实现中，对于给定的哈希函数 $f(x) = x \% n$，有一长度为 $n$ 的数组用于存储 $x \geq 0$ 的值。

当需要向哈希表插入一个值 $x$ 时，从数组的下标 $f(x)$ 开始，向右循环移动，找到第一个未存储该数的位置，写入 $x$。若哈希表已满或 $x$ 已存在于表中，则不再插入 $x$。

给定 $n$ 个整数 $a_i$ ($a_i \geq -1$) 表示哈希表数组中存储的元素，$-1$ 表示当前位置未写入数据。

请按插入哈希表的顺序输出原序列（假设插入过程中不存在相同的数字），如果有多个满足条件的序列，输出字典序最小的。

输入描述

• 第一行为一个正整数 $n$。
• 第二行为 $n$ 个整数 $a_1, a_2, \dots, a_n$，含义如题。输入保证序列为通过线性探测法插入的哈希表结果。（除 $a_i = -1$ 外，其它数字两两互不相等。）

输出描述

• 输出 $l$ 个非负整数，表示插入哈希表后的原序列，其中 $l$ 为哈希表中非 $-1$ 的整数个数。

补充说明

• 对于 30% 的数据，$1 \leq n \leq 10$；
• 对于 60% 的数据，$1 \leq n \leq 1000$；
• 对于 100% 的数据，$1 \leq n \leq 10^5$，$-1 \leq a_i \leq 10^9$。

样例输入输出

5
-1 1 -1 3 4

1 3 4

5
9 1 8 3 4

1 3 4 9 8

说明

【样例 #1】

由于没有冲突，原序列可以是 $[1,3,4]$ 的任意一种排列组合，而其中 $[1,3,4]$ 是所有可能的结果中字典序最小的一种。

【样例 #2】

数据插入过程如下：$[-1, -1, -1, -1, -1]$$\to$$[-1, 1, -1, -1, -1]$$\to$$[-1, 1, -1, 3, -1]$$\to$$[-1, 1, -1, 3, 4]$$\to$$[9, 1, -1, 3, 4]$$\to$$[9, 1, 8, 3, 4]$。

若按 $[1, 3, 4, 8, 9]$ 顺序插入，将得到结果 $[8, 1, 9, 3, 4]$，与输入不符，因此不存在字典序更小的插入顺序。