codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2077A.md (2050B)


      1 Source: https://codeforces.com/problemset/problem/2077/A
      2 
      3 A. Breach of Faith
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 [Breach of Faith - Supire feat.eili](https://www.youtube.com/watch?v=nVTiCKIIQSM)
     22 
     23 You and your team have worked tirelessly until you have a sequence $a_1, a_2, \ldots, a_{2n+1}$ of positive integers satisfying these properties.
     24 
     25 * $1 \le a_i \le 10^{18}$ for all $1 \le i \le 2n + 1$.
     26 * $a_1, a_2, \ldots, a_{2n+1}$ are pairwise distinct.
     27 * $a_1 = a_2 - a_3 + a_4 - a_5 + \ldots + a_{2n} - a_{2n+1}$.
     28 
     29 However, the people you worked with sabotaged you because they wanted to publish this sequence first. They deleted one number from this sequence and shuffled the rest, leaving you with a sequence $b_1, b_2, \ldots, b_{2n}$. You have forgotten the sequence $a$ and want to find a way to recover it.
     30 
     31 If there are many possible sequences, you can output any of them. It can be proven under the constraints of the problem that at least one sequence $a$ exists.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     36 
     37 The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).
     38 
     39 The second line of each test case contains $2n$ distinct integers $b_1, b_2, \ldots, b_{2n}$ ($1 \leq b_i \leq 10^9$), denoting the sequence $b$.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output $2n+1$ distinct integers, denoting the sequence $a$ ($1 \leq a_i \leq 10^{18}$).
     46 
     47 If there are multiple possible sequences, you can output any of them. The sequence $a$ should satisfy the given conditions, and it should be possible to obtain $b$ after deleting one element from $a$ and shuffling the remaining elements.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 1
     57 
     58 9 2
     59 
     60 2
     61 
     62 8 6 1 4
     63 
     64 3
     65 
     66 99 2 86 33 14 77
     67 
     68 2
     69 
     70 1 6 3 2
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 7 9 2
     77 1 8 4 6 9
     78 86 99 2 77 69 14 33
     79 4 6 1 2 3
     80 ```