D. Gluttony

Codeforces

IDCF892D

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

Let $ a = (a_1, a_2, \dots, a_n) $ be a sequence of $ n $ distinct integers. Find a permutation $ b = (b_1, b_2, \dots, b_n) $ of $ a $ such that for every non-empty proper subset $ S \subsetneq \{1, 2, \dots, n\} $, $$ \sum_{i \in S} a_i \ne \sum_{i \in S} b_i. $$ If no such $ b $ exists, output $-1$.

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": "D. 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": "CF892D"
  },
  "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]$。请构造一个数组 $[b]$，它是 $[a]$ 的一个排列，使得对于每一个非空真子集的索引集合 $S = \\{x_1, x_2, \\dots, x_k\\}$（其中 $1 \\leq x_i \\leq n$，且 $0 < k < n$），在 $[a]$ 和 $[b]$ 中这些位置上的元素之和均不相等，即 \n\n第一行包含一个整数 $n$（$1 \\le...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ a = (a_1, a_2, \\dots, a_n) $ be a sequence of $ n $ distinct integers.  \nFind a permutation $ b = (b_1, b_2, \\dots, b_n) $ of $ a $ such that for every non-empty proper subset $ S \\subsetneq \\{1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments