P. Proooooooooooooofer

Codeforces

IDCF10051P

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given an encrypted string, encrypted using a certain algorithm. Decrypt it! Encryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n and a is a sequence of integers of length n - 2. The first line, contains an integer n. (3 ≤ n ≤ 105). The second line, contains string s. The third line contains n - 2 integers a1, a2, ..., an - 2 seperated by space. Each character of s is a lower case English letter (1 ≤ ai ≤ n and 1 ≤ i ≤ n - 2). Print t in the only line of output. ## Input The first line, contains an integer n. (3 ≤ n ≤ 105).The second line, contains string s. The third line contains n - 2 integers a1, a2, ..., an - 2 seperated by space.Each character of s is a lower case English letter (1 ≤ ai ≤ n and 1 ≤ i ≤ n - 2). ## Output Print t in the only line of output. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 10^5 $. Let $ s \in \Sigma^n $ be a string over $ \Sigma = \{a, b, \dots, z\} $. Let $ a = (a_1, a_2, \dots, a_{n-2}) \in \mathbb{Z}^{n-2} $ with $ 1 \leq a_i \leq n $. **Constraints** 1. $ 3 \leq n \leq 10^5 $ 2. $ s $ consists of lowercase English letters. 3. $ 1 \leq a_i \leq n $ for all $ i \in \{1, \dots, n-2\} $ **Objective** Recover the original string $ t \in \Sigma^n $ such that the encryption process producing $ (s, a) $ from $ t $ is inverted. *(The encryption algorithm is implied to be: for $ i = 1 $ to $ n-2 $, $ a_i $ is the 1-based index in $ t $ of the character that was removed at step $ i $, and $ s $ is the sequence of removed characters. Thus, decryption reconstructs $ t $ by inserting each character $ s_i $ back into position $ a_i $ in an initially empty or placeholder array.)* Formally, reconstruct $ t $ such that: - Initialize an array $ t $ of $ n $ placeholders. - For each $ i \in \{1, \dots, n-2\} $, place $ s_i $ at position $ a_i $ in $ t $. - The two remaining positions in $ t $ (not assigned by any $ a_i $) are filled with the last two characters of $ s $, in order, into the unassigned indices in increasing order. Then output $ t $.

API Response (JSON)

{
  "problem": {
    "name": "P. Proooooooooooooofer",
    "description": {
      "content": "You are given an encrypted string, encrypted using a certain algorithm. Decrypt it! Encryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10051P"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an encrypted string, encrypted using a certain algorithm. Decrypt it!\n\nEncryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 10^5 $.  \nLet $ s \\in \\Sigma^n $ be a string over $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ a = (a_1, a_2, \\dots, a_{n-2}) \\in \\mathbb{Z}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments