题目详情题解（0）讨论（0）提交记录（0）

AT_arc103_d.[ARC103F] Distance Sums

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 的数列 D1,D2,…,DND_1, D_2, \ldots, D_N。所有 DiD_i 的值都互不相同。请问是否存在一个具有 NN 个顶点的树满足以下条件？

  • 每个顶点都标有 1,2,…,N1, 2, \ldots, N 的编号
  • 每条边都标有 1,2,…,N−11, 2, \ldots, N-1 的编号，第 ii 条边连接顶点 uiu_i 和 viv_i
  • 对于每个顶点 ii，从 ii 到其他所有顶点的距离之和为 DiD_i。这里，每条边的长度都视为 11。

如果存在满足条件的树，请构造出其中一个。

输入格式

输入以以下格式通过标准输入给出。

$ N $ $ D_1 $ $ D_2 $ $ : $ $ D_N $

输出格式

如果不存在满足条件的树，输出 -1。

如果存在满足条件的树，输出 N−1N-1 行。第 ii 行输出 ui,viu_i, v_i，以空格分隔。如果存在多个满足条件的树，输出其中任何一个即可。

输入输出样例

  • 输入#1

    7
10
15
13
18
11
14
19

    输出#1

    1 2
1 3
1 5
3 4
5 6
6 7

  • 输入#2

    2
1
2

    输出#2

    -1

  • 输入#3

    15
57
62
47
45
42
74
90
75
54
50
66
63
77
87
51

    输出#3

    1 10
1 11
2 8
2 15
3 5
3 9
4 5
4 10
5 15
6 12
6 14
7 13
9 12
11 13

说明/提示

数据范围

  • $ 2\ \leq\ N\ \leq\ 100000 $
  • $ 1\ \leq\ D_i\ \leq\ 10^{12} $
  • $ D_i $ 互不相同

样例解释 1

存在如下满足条件的树：

输入解题思路，AI测评打分。不知道怎么写?

首页