D. Picture Day

Codeforces

IDCF10219D

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You have a class of even number of students n. The class can be divided into n / 2 pairs of best friends, who always like to stay next to each other. Unfortunately, this makes your job harder because today is picture day. For a perfect picture, you want to align the students in order of non-decreasing heights then non-increasing heights. Each pair of best friends must be next to each other, however, their relative order does not matter (friends a and b ordered as ab or ba both work). For example, [1, 2, 4, 3, 3, 1] ,[1, 5, 10, 11], [11, 10, 5, 5], [3, 3, 3, 3] are perfect height arrangements as numbers first do not decrease, then they do not increase. Given the pairs of best friends, can you arrange them to make a perfect picture? The first line of input contains a single *even* integer n (2 ≤ n ≤ 3 × 105), the number of students in the class. Each of the following n / 2 lines contains two integers ha hb (1 ≤ ha, hb ≤ 109), the heights of a pair of best friends in the class. Output *any* valid arrangement of the class' heights such that each pair of best friends are standing next to each other. If there is no answer, output *-1* on a single line. ## Input The first line of input contains a single *even* integer n (2 ≤ n ≤ 3 × 105), the number of students in the class.Each of the following n / 2 lines contains two integers ha hb (1 ≤ ha, hb ≤ 109), the heights of a pair of best friends in the class. ## Output Output *any* valid arrangement of the class' heights such that each pair of best friends are standing next to each other.If there is no answer, output *-1* on a single line. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be an even integer, $ n \geq 2 $. Let $ P = \{(h_{i,1}, h_{i,2}) \mid i \in \{1, \dots, n/2\}\} $ be a set of $ n/2 $ pairs of student heights. **Constraints** 1. $ 2 \leq n \leq 3 \times 10^5 $ 2. For each pair $ (h_{i,1}, h_{i,2}) \in P $, $ 1 \leq h_{i,1}, h_{i,2} \leq 10^9 $ **Objective** Determine if there exists a sequence $ H = (h_1, h_2, \dots, h_n) $ such that: - Each pair $ (h_{i,1}, h_{i,2}) \in P $ appears as two adjacent elements in $ H $, in either order $ (h_{i,1}, h_{i,2}) $ or $ (h_{i,2}, h_{i,1}) $. - The sequence $ H $ is *unimodal*: there exists an index $ k \in \{1, \dots, n\} $ such that: $$ h_1 \leq h_2 \leq \cdots \leq h_k \geq h_{k+1} \geq \cdots \geq h_n $$ If such $ H $ exists, output any valid arrangement; otherwise, output $-1$.

API Response (JSON)

{
  "problem": {
    "name": "D. Picture Day",
    "description": {
      "content": "You have a class of even number of students n. The class can be divided into n / 2 pairs of best friends, who always like to stay next to each other. Unfortunately, this makes your job harder because ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10219D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a class of even number of students n. The class can be divided into n / 2 pairs of best friends, who always like to stay next to each other. Unfortunately, this makes your job harder because ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be an even integer, $ n \\geq 2 $.  \nLet $ P = \\{(h_{i,1}, h_{i,2}) \\mid i \\in \\{1, \\dots, n/2\\}\\} $ be a set of $ n/2 $ pairs of student heights.  \n\n**Constr...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments