A. Mr. Skeleton

Codeforces

IDCF10278A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Mr. Skeleton is a groovy guy. He has $N$ bones. Wait, wait a minute, he _thought_ he had $N$ bones. 1, 2, 3, 4...aw crap, not again. He swears he had $N$, they were just here! Well, it's hard being a skeleton, and sometimes you just have to pick yourself up off the ground, even if that means literally. As in literally going back and picking up pieces of your body where they fell off and you forgot them. Help Mr. Skeleton figure out which bones he's missing this time. Given that Mr. Skeleton normally has bones $1$ through $N$ and now he only has some subset of those bones still attached, $H$ of them to be precise, compute the list of lost bones that Mr. Skeleton has left to find! The first line contains two integers: $N$ ($1 <= N <= 10^5$), the total number of bones that Mr. Skeleton normally has when he has all of his bones, and $H$ ($1 <= H <= N$), the number of bones he currently has on him. The next $H$ lines each contain the name $b_i$ ($1 <= b_i <= N$) of one of Mr. Skeleton's unique bones that he has verified is currently in his possession (i.e. not missing). Print out the numeric name of each bone that Mr. Skeleton is still missing. The bone names should be printed out on separate lines, in order from least to greatest number. ## Input The first line contains two integers: $N$ ($1 <= N <= 10^5$), the total number of bones that Mr. Skeleton normally has when he has all of his bones, and $H$ ($1 <= H <= N$), the number of bones he currently has on him. The next $H$ lines each contain the name $b_i$ ($1 <= b_i <= N$) of one of Mr. Skeleton's unique bones that he has verified is currently in his possession (i.e. not missing). ## Output Print out the numeric name of each bone that Mr. Skeleton is still missing. The bone names should be printed out on separate lines, in order from least to greatest number. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the array. Let $ A = [1, 2, 3, \dots, n] $ be the initial array. Let $ (a_i, b_i) \in \{1, \dots, n\}^2 $ for $ i = 1, \dots, n $ be the pairs of indices specifying swap operations. **Constraints** 1. $ 1 \le n \le 5 \cdot 10^5 $ 2. $ 1 \le a_i, b_i \le n $ for all $ i \in \{1, \dots, n\} $ 3. If $ a_i = b_i $, no swap occurs. **Objective** For each $ i \in \{1, \dots, n\} $, perform the swap: $$ \text{if } a_i \ne b_i, \quad A[a_i] \leftrightarrow A[b_i] $$ (where indices are 1-based). Output the final state of array $ A $.

API Response (JSON)

{
  "problem": {
    "name": "A. Mr. Skeleton",
    "description": {
      "content": "Mr. Skeleton is a groovy guy. He has $N$ bones. Wait, wait a minute, he _thought_ he had $N$ bones. 1, 2, 3, 4...aw crap, not again. He swears he had $N$, they were just here! Well, it's hard being a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10278A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mr. Skeleton is a groovy guy. He has $N$ bones. Wait, wait a minute, he _thought_ he had $N$ bones. 1, 2, 3, 4...aw crap, not again. He swears he had $N$, they were just here!\n\nWell, it's hard being a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ A = [1, 2, 3, \\dots, n] $ be the initial array.  \nLet $ (a_i, b_i) \\in \\{1, \\dots, n\\}^2 $ for $ i = 1, \\dots, n $ be t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments