M. Last Man Standing

Codeforces

IDCF10134M

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A company of n friends decided to play a multiplayer shooter in the Last Man Standing mode. The distinctive feature of this mode is when a player is killed, he does not respawn, but waits a round to finish. A round finishes when there is only one player alive. You are given a notarized screenshot of the current fight results, made during the first round of the game. It provides an information about how many kills each player has made. You want to check if it's a fake or not, i.e. whether such situation could occur during the game. The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of players. The second line contains n integers ai separated by a space (0 ≤ ai ≤ 109) — the numbers of kills made by each player. These numbers are given in non-increasing order. If such situation was not possible in the game, output «_NO_» (without quotes). Otherwise, in the first line output «_YES_» (without quotes), and then output a log of kills in the round, consisting of k pairs of integers, where k is the total number of kills made at the moment of taking the screenshot. Each pair of integers in the log must consist of the number of the player who made the kill, and the number of the killed player, exactly in this order. Records in the log must be ordered chronologically. If there are several correct logs, output any of them. ## Input The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of players.The second line contains n integers ai separated by a space (0 ≤ ai ≤ 109) — the numbers of kills made by each player. These numbers are given in non-increasing order. ## Output If such situation was not possible in the game, output «_NO_» (without quotes).Otherwise, in the first line output «_YES_» (without quotes), and then output a log of kills in the round, consisting of k pairs of integers, where k is the total number of kills made at the moment of taking the screenshot. Each pair of integers in the log must consist of the number of the player who made the kill, and the number of the killed player, exactly in this order. Records in the log must be ordered chronologically. If there are several correct logs, output any of them. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of players. Let $ A = (a_1, a_2, \dots, a_n) $ be a non-increasing sequence of non-negative integers, where $ a_i $ is the number of kills made by player $ i $. **Constraints** 1. $ 1 \leq n \leq 200000 $ 2. $ 0 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 3. $ a_1 \geq a_2 \geq \dots \geq a_n $ **Objective** Determine whether there exists a valid sequence of kills (a chronological log) such that: - Each kill is an ordered pair $ (x, y) $, where player $ x $ kills player $ y $, and $ x \ne y $. - No player can kill after being killed. - At the end of the round, exactly one player remains alive (all others are dead). - The total number of kills by player $ i $ is exactly $ a_i $. If such a sequence exists, output "YES" followed by any valid log of $ k = \sum_{i=1}^n a_i $ kills. Otherwise, output "NO".

API Response (JSON)

{
  "problem": {
    "name": "M. Last Man Standing",
    "description": {
      "content": "A company of n friends decided to play a multiplayer shooter in the Last Man Standing mode. The distinctive feature of this mode is when a player is killed, he does not respawn, but waits a round to f",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10134M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A company of n friends decided to play a multiplayer shooter in the Last Man Standing mode. The distinctive feature of this mode is when a player is killed, he does not respawn, but waits a round to f...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of players.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a non-increasing sequence of non-negative integers, where $ a_i $ is the number of kills ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments