E. Encryption of Orz Pandas

Codeforces

IDCF10287E

Time5000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

An Orz Panda agent has some data which should be encrypted. He has store the data into a list _a_ with length _n_. To encrypt it, he'll run the following loop (wrote in Python) for $k$ times: Please output the content of the list _a_ after the encryption. There is only one test case in the input file. The first line contains two integers $n$ and $k$, seperated by a whitespace. The second line contains $n$ integers $a_0, a_1, \\\\cdots, a_{n -1}$, the elements in the list _a_. Each adjacent pair of integers are seperated by a whitespace. It's guaranteed that $1 <= n <= 10^5$, $0 <= a_i < 2^(17)$, and $1 <= k <= 10^(18)$. Output one line, containing $n$ integers in the encrypted list _a_. Each adjacent pair of integers should be seperated by a whitespace. There should be no trailing whitespaces. For the example: ## Input There is only one test case in the input file.The first line contains two integers $n$ and $k$, seperated by a whitespace.The second line contains $n$ integers $a_0, a_1, \\\\cdots, a_{n -1}$, the elements in the list _a_. Each adjacent pair of integers are seperated by a whitespace.It's guaranteed that $1 <= n <= 10^5$, $0 <= a_i < 2^(17)$, and $1 <= k <= 10^(18)$. ## Output Output one line, containing $n$ integers in the encrypted list _a_. Each adjacent pair of integers should be seperated by a whitespace. There should be no trailing whitespaces. [samples] ## Note For the example: The list should become _[1,1,4,5,0,5]_ after the first iteration The list should become _[1,0,4,1,1,4]_ after the second iteration The list should become _[1,1,5,4,5,1]_ after the third iteration The list should become _[1,0,5,1,4,5]_ after the fourth iteration The list should become _[1,1,4,5,1,4]_ after the fifth iteration, and you should output it

**Definitions** Let $ s \in \Sigma^n $ be a string of length $ n $, where $ \Sigma = \{a, b, \dots, z\} $. For any prefix $ s[1..i] $ (where $ 1 \leq i \leq n $), a substring $ s[l..r] \subseteq s[1..i] $ is an *eigen substring* if it occurs exactly once in $ s[1..i] $. **Constraints** 1. $ 1 \leq n \leq 10^6 $ 2. All characters in $ s $ are lowercase English letters. **Objective** For each $ i \in \{1, \dots, n\} $, compute: $$ L_i = \min \{ r - l + 1 \mid s[l..r] \text{ is an eigen substring of } s[1..i] \} $$ If no eigen substring exists, define $ L_i = \infty $ (though guaranteed to exist due to single-character substrings).

API Response (JSON)

{
  "problem": {
    "name": "E. Encryption of Orz Pandas",
    "description": {
      "content": "An Orz Panda agent has some data which should be encrypted. He has store the data into a list _a_ with length _n_. To encrypt it, he'll run the following loop (wrote in Python) for $k$ times: Please ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10287E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "An Orz Panda agent has some data which should be encrypted. He has store the data into a list _a_ with length _n_. To encrypt it, he'll run the following loop (wrote in Python) for $k$ times:\n\nPlease ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^n $ be a string of length $ n $, where $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nFor any prefix $ s[1..i] $ (where $ 1 \\leq i \\leq n $), a substring $ s[l..r] \\subseteq s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments