{"problem":{"name":"[蓝桥杯 2024 国 A] 兔子集结","description":{"content":"在森林幽静的一隅，有一村落居住着 $n$ 只兔子。 某个月光皎洁的夜晚，这些兔子列成一队，准备开始一场集结跳跃活动。村落中的每只兔子都占据一个位置，对于第 $i$ 只兔子，其位置为 $p_i$。我们称位置较小的为左边，位置较大的为右边。 按照兔子村落的习俗，每只兔子都会选择距离自己最近的兔子作为同伴，并向同伴所在的方向进行跳跃。如果一只兔子左边和右边的兔子距离它一样近，那么它会选择左边的兔子作","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10577"},"statements":[{"statement_type":"Markdown","content":"在森林幽静的一隅，有一村落居住着 $n$ 只兔子。\n\n某个月光皎洁的夜晚，这些兔子列成一队，准备开始一场集结跳跃活动。村落中的每只兔子都占据一个位置，对于第 $i$ 只兔子，其位置为 $p_i$。我们称位置较小的为左边，位置较大的为右边。\n\n按照兔子村落的习俗，每只兔子都会选择距离自己最近的兔子作为同伴，并向同伴所在的方向进行跳跃。如果一只兔子左边和右边的兔子距离它一样近，那么它会选择左边的兔子作为同伴。\n\n兔子的每次跳跃，只能向左或向右移动一个单位距离。也就是说，如果一只兔子当前位于 $x$ 的位置，那么它下一次跳跃后会到达 $x-1$ 或者 $x+1$ 的位置。\n\n当两只相互靠近的兔子之间的距离为 $1$ 时，左边的兔子会停在原地，而右边的兔子会跳到左边兔子的位置上，完成集结。\n\n兔子们会一直跳跃，直到与自己最初选择的同伴完成集结后停下。\n\n请问，当所有兔子都完成集结后，每只兔子都分别位于哪个位置上？\n\n## Input\n\n输入的第一行包含一个整数 $n$，表示兔子的数量。\n第二行包含 $n$ 个整数 $p_1,p_2,\\cdots, p_n$，相邻整数之间使用一个空格分隔，表示每只兔子的初始位置。\n\n## Output\n\n输出一行包含 $n$ 个整数，表示每只兔子完成集结后的位置。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n兔子 $1$ 选择的同伴为兔子 $5$，兔子 $5$ 选择的同伴为兔子 $1$。由于它们彼此间的距离为 $1$，因此兔子 $5$ 会停在原地，而兔子 $1$ 会跳到位置 $1$ 上，与兔子 $5$完成集结。\n\n兔子 $2$ 选择的同伴为兔子 $3$，兔子 $4$ 选择的同伴也为兔子3。对于兔子 $3$ 来说，兔子 $2$ 和兔子 $4$ 与它的距离相同，所以它会选择左边的兔子 $2$ 作为同伴。兔子 $2$ 会向右跳一个位置，兔子 $3$ 会向左跳一个位置，兔子 $4$ 会向左跳一个位置。此时，兔子 $2$ 和兔子 $3$ 均位于位置 $6$，完成集结（停止跳跃）。兔子 $4$ 会继续向左跳跃，直到跳到位置 $6$ 后与兔子 $3$ 完成集结。\n\n**【评测用例规模与约定】**\n\n对于 $40\\%$ 的评测用例，$2\\le n\\le 500$，$1\\le p_i\\le 10^5$，$p_1,p_2,\\cdots,p_n$ 各不相同。  \n对于所有评测用例，$2\\le n \\le 10^5$，$1 \\le p_i \\le 10^9$，$p_1,p_2,\\cdots,p_n$ 各不相同。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10577","tags":["并查集","2024","排序","蓝桥杯国赛"],"sample_group":[["5\n2 5 7 9 1","1 6 6 6 1"]],"created_at":"2026-03-03 11:09:25"}}