C. Swap Adjacent Elements

Codeforces

IDCF920C

Time1000ms

Memory256MB

Difficulty—

dfs and similargreedymathsortingstwo pointers

English · Original

Chinese · Translation

Formal · Original

You have an array _a_ consisting of _n_ integers. Each integer from 1 to _n_ appears exactly once in this array. For some indices _i_ (1 ≤ _i_ ≤ _n_ - 1) it is possible to swap _i_\-th element with (_i_ + 1)\-th, for other indices it is not possible. You may perform any number of swapping operations any order. There is no limit on the number of times you swap _i_\-th element with (_i_ + 1)\-th (if the position is not forbidden). Can you make this array sorted in ascending order performing some sequence of swapping operations? ## Input The first line contains one integer _n_ (2 ≤ _n_ ≤ 200000) — the number of elements in the array. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 200000) — the elements of the array. Each integer from 1 to _n_ appears exactly once. The third line contains a string of _n_ - 1 characters, each character is either _0_ or _1_. If _i_\-th character is _1_, then you can swap _i_\-th element with (_i_ + 1)\-th any number of times, otherwise it is forbidden to swap _i_\-th element with (_i_ + 1)\-th. ## Output If it is possible to sort the array in ascending order using any sequence of swaps you are allowed to make, print _YES_. Otherwise, print _NO_. [samples] ## Note In the first example you may swap _a_3 and _a_4, and then swap _a_4 and _a_5.

你有一个包含 $n$ 个整数的数组 $[a]$。数组中的每个整数从 $1$ 到 $n$ 恰好出现一次。对于某些索引 $i$（$1 ≤ i ≤ n - 1$），你可以交换第 $i$ 个元素与第 $(i + 1)$ 个元素；而对于其他索引，这种交换是不允许的。你可以执行任意次数的交换操作，且顺序任意。对于非禁止的位置，你可以任意多次交换第 $i$ 个元素与第 $(i + 1)$ 个元素。你能否通过执行某些交换操作序列，使该数组按升序排列？第一行包含一个整数 $n$（$2 ≤ n ≤ 200000$）——数组中元素的个数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 200000$）——数组的元素。每个从 $1$ 到 $n$ 的整数恰好出现一次。第三行包含一个长度为 $n - 1$ 的字符串，每个字符为 _0_ 或 _1_。如果第 $i$ 个字符是 _1_，则你可以任意多次交换第 $i$ 个元素与第 $(i + 1)$ 个元素；否则，这种交换是被禁止的。如果你可以通过允许的交换操作序列将数组排序为升序，请输出 _YES_；否则，输出 _NO_。在第一个示例中，你可以交换 $a_3$ 和 $a_4$，然后交换 $a_4$ 和 $a_5$。 ## Input 第一行包含一个整数 $n$（$2 ≤ n ≤ 200000$）——数组中元素的个数。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 200000$）——数组的元素。每个从 $1$ 到 $n$ 的整数恰好出现一次。第三行包含一个长度为 $n - 1$ 的字符串，每个字符为 _0_ 或 _1_。如果第 $i$ 个字符是 _1_，则你可以任意多次交换第 $i$ 个元素与第 $(i + 1)$ 个元素；否则，这种交换是被禁止的。 ## Output 如果你可以通过允许的交换操作序列将数组排序为升序，请输出 _YES_；否则，输出 _NO_。 [samples] ## Note 在第一个示例中，你可以交换 $a_3$ 和 $a_4$，然后交换 $a_4$ 和 $a_5$。

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $. Let $ S \in \{0,1\}^{n-1} $ be a binary string where $ S[i] = 1 $ indicates that swapping $ a_i $ and $ a_{i+1} $ is permitted, for $ i \in \{1, \dots, n-1\} $. **Constraints** 1. $ 2 \leq n \leq 200000 $ 2. $ A $ is a permutation of $ \{1, 2, \dots, n\} $ 3. $ S[i] \in \{0,1\} $ for all $ i \in \{1, \dots, n-1\} $ **Objective** Determine whether $ A $ can be sorted into ascending order $ (1, 2, \dots, n) $ using any number of adjacent swaps, where swaps at position $ i $ are allowed if and only if $ S[i] = 1 $.

Samples

Input #1

6
1 2 5 3 4 6
01110

Output #1

YES

Input #2

6
1 2 5 3 4 6
01010

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "C. Swap Adjacent Elements",
    "description": {
      "content": "You have an array _a_ consisting of _n_ integers. Each integer from 1 to _n_ appears exactly once in this array. For some indices _i_ (1 ≤ _i_ ≤ _n_ - 1) it is possible to swap _i_\\-th element with (",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF920C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have an array _a_ consisting of _n_ integers. Each integer from 1 to _n_ appears exactly once in this array.\n\nFor some indices _i_ (1 ≤ _i_ ≤ _n_ - 1) it is possible to swap _i_\\-th element with (...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你有一个包含 $n$ 个整数的数组 $[a]$。数组中的每个整数从 $1$ 到 $n$ 恰好出现一次。\n\n对于某些索引 $i$（$1 ≤ i ≤ n - 1$），你可以交换第 $i$ 个元素与第 $(i + 1)$ 个元素；而对于其他索引，这种交换是不允许的。你可以执行任意次数的交换操作，且顺序任意。对于非禁止的位置，你可以任意多次交换第 $i$ 个元素与第 $(i + 1)$ 个元素。\n\n你能否...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nLet $ S \\in \\{0,1\\}^{n-1} $ be a binary string...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments