B. Distances to Zero

Codeforces

IDCF803B

Time2000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

You are given the array of integer numbers _a_0, _a_1, ..., _a__n_ - 1. For each element find the distance to the nearest zero (to the element which equals to zero). There is at least one zero element in the given array. ## Input The first line contains integer _n_ (1 ≤ _n_ ≤ 2·105) — length of the array _a_. The second line contains integer elements of the array separated by single spaces ( - 109 ≤ _a__i_ ≤ 109). ## Output Print the sequence _d_0, _d_1, ..., _d__n_ - 1, where _d__i_ is the difference of indices between _i_ and nearest _j_ such that _a__j_ = 0. It is possible that _i_ = _j_. [samples]

给定一个整数数组 #cf_span[a0, a1, ..., an - 1]。对于每个元素，求其到最近的零元素（值为零的元素）的距离。给定数组中至少有一个零元素。第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 数组 #cf_span[a] 的长度。第二行包含用空格分隔的数组元素 (#cf_span[ - 109 ≤ ai ≤ 109])。请输出序列 #cf_span[d0, d1, ..., dn - 1]，其中 #cf_span[di] 是下标 #cf_span[i] 与最近的下标 #cf_span[j] 之间的差值，满足 #cf_span[aj = 0]。允许 #cf_span[i = j]。 ## Input 第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 数组 #cf_span[a] 的长度。第二行包含用空格分隔的数组元素 (#cf_span[ - 109 ≤ ai ≤ 109])。 ## Output 请输出序列 #cf_span[d0, d1, ..., dn - 1]，其中 #cf_span[di] 是下标 #cf_span[i] 与最近的下标 #cf_span[j] 之间的差值，满足 #cf_span[aj = 0]。允许 #cf_span[i = j]。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ denote the length of the array. Let $ A = (a_0, a_1, \dots, a_{n-1}) $ be a sequence of integers where $ \exists\, j \in \{0, \dots, n-1\} $ such that $ a_j = 0 $. Let $ Z = \{ j \in \{0, \dots, n-1\} \mid a_j = 0 \} $ be the set of indices where the element is zero. **Constraints** 1. $ 1 \leq n \leq 2 \cdot 10^5 $ 2. $ -10^9 \leq a_i \leq 10^9 $ for all $ i \in \{0, \dots, n-1\} $ 3. $ Z \neq \emptyset $ **Objective** For each $ i \in \{0, \dots, n-1\} $, compute: $$ d_i = \min_{j \in Z} |i - j| $$ Output the sequence $ (d_0, d_1, \dots, d_{n-1}) $.

Samples

Input #1

9
2 1 0 3 0 0 3 2 4

Output #1

2 1 0 1 0 0 1 2 3

Input #2

5
0 1 2 3 4

Output #2

0 1 2 3 4

Input #3

7
5 6 0 1 -2 3 4

Output #3

2 1 0 1 2 3 4

API Response (JSON)

{
  "problem": {
    "name": "B. Distances to Zero",
    "description": {
      "content": "You are given the array of integer numbers _a_0, _a_1, ..., _a__n_ - 1. For each element find the distance to the nearest zero (to the element which equals to zero). There is at least one zero element",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF803B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given the array of integer numbers _a_0, _a_1, ..., _a__n_ - 1. For each element find the distance to the nearest zero (to the element which equals to zero). There is at least one zero element...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个整数数组 #cf_span[a0, a1, ..., an - 1]。对于每个元素，求其到最近的零元素（值为零的元素）的距离。给定数组中至少有一个零元素。\n\n第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 数组 #cf_span[a] 的长度。第二行包含用空格分隔的数组元素 (#cf_span[ - 109 ≤ ai ≤ 109])。\n\n请...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ denote the length of the array.  \nLet $ A = (a_0, a_1, \\dots, a_{n-1}) $ be a sequence of integers where $ \\exists\\, j \\in \\{0, \\dots, n-1\\} $ such that $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments