B. Gluttony

Codeforces

IDCF891B

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgreedy

English · Original

Chinese · Translation

Formal · Original

You are given an array _a_ with _n_ distinct integers. Construct an array _b_ by permuting _a_ such that for every non-empty subset of indices _S_ = {_x_1, _x_2, ..., _x__k_} (1 ≤ _x__i_ ≤ _n_, 0 < _k_ < _n_) the sums of elements on that positions in _a_ and _b_ are different, i. e. ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 22) — the size of the array. The second line contains _n_ space-separated distinct integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 109) — the elements of the array. ## Output If there is no such array _b_, print _\-1_. Otherwise in the only line print _n_ space-separated integers _b_1, _b_2, ..., _b__n_. Note that _b_ must be a permutation of _a_. If there are multiple answers, print any of them. [samples] ## Note An array _x_ is a permutation of _y_, if we can shuffle elements of _y_ such that it will coincide with _x_. Note that the empty subset and the subset containing all indices are not counted.

给你一个包含 $n$ 个互不相同整数的数组 $[a]$。请通过重排 $[a]$ 构造一个数组 $[b]$，使得对于每一个非空真子集的索引集合 $S = \{x_1, x_2, \dots, x_k\}$（其中 $1 \le x_i \le n$，且 $0 < k < n$），在 $[a]$ 和 $[b]$ 中这些位置上的元素之和均不相等，即第一行包含一个整数 $n$（$1 \le n \le 22$）——数组的大小。第二行包含 $n$ 个空格分隔的互不相同的整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）——数组的元素。如果不存在这样的数组 $[b]$，请输出 _-1_。否则，在唯一的一行中输出 $n$ 个空格分隔的整数 $b_1, b_2, \dots, b_n$。注意 $[b]$ 必须是 $[a]$ 的一个排列。如果有多个答案，输出任意一个即可。数组 $[x]$ 是 $[y]$ 的一个排列，当且仅当我们可以对 $[y]$ 的元素重新排序使其与 $[x]$ 完全一致。注意：空子集和包含所有索引的子集不计入。 ## Input 第一行包含一个整数 $n$（$1 \le n \le 22$）——数组的大小。第二行包含 $n$ 个空格分隔的互不相同的整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）——数组的元素。 ## Output 如果不存在这样的数组 $[b]$，请输出 _-1_。否则，在唯一的一行中输出 $n$ 个空格分隔的整数 $b_1, b_2, \dots, b_n$。注意 $[b]$ 必须是 $[a]$ 的一个排列。如果有多个答案，输出任意一个即可。 [samples] ## Note 数组 $[x]$ 是 $[y]$ 的一个排列，当且仅当我们可以对 $[y]$ 的元素重新排序使其与 $[x]$ 完全一致。注意：空子集和包含所有索引的子集不计入。

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 22 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of $ n $ distinct integers, $ 0 \leq a_i \leq 10^9 $. Let $ B = (b_1, b_2, \dots, b_n) $ be a permutation of $ A $. **Constraints** For every non-empty proper subset $ S \subset \{1, 2, \dots, n\} $, $ 0 < |S| < n $, $$ \sum_{i \in S} a_i \ne \sum_{i \in S} b_i $$ **Objective** Find such a permutation $ B $ of $ A $, or output $-1$ if none exists.

Samples

Input #1

2
1 2

Output #1

2 1

Input #2

4
1000 100 10 1

Output #2

100 1 1000 10

API Response (JSON)

{
  "problem": {
    "name": "B. Gluttony",
    "description": {
      "content": "You are given an array _a_ with _n_ distinct integers. Construct an array _b_ by permuting _a_ such that for every non-empty subset of indices _S_ = {_x_1, _x_2, ..., _x__k_} (1 ≤ _x__i_ ≤ _n_, 0 < _k",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF891B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an array _a_ with _n_ distinct integers. Construct an array _b_ by permuting _a_ such that for every non-empty subset of indices _S_ = {_x_1, _x_2, ..., _x__k_} (1 ≤ _x__i_ ≤ _n_, 0 < _k...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你一个包含 $n$ 个互不相同整数的数组 $[a]$。请通过重排 $[a]$ 构造一个数组 $[b]$，使得对于每一个非空真子集的索引集合 $S = \\{x_1, x_2, \\dots, x_k\\}$（其中 $1 \\le x_i \\le n$，且 $0 < k < n$），在 $[a]$ 和 $[b]$ 中这些位置上的元素之和均不相等，即\n\n第一行包含一个整数 $n$（$1 \\le n \\le ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 22 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of $ n $ distinct integers, $ 0 \\leq a_i \\leq 10^9 $.  \nLet $ B = (b_1, b_2, \\dots,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments