A. Zebras

Codeforces

IDCF949A

Time1000ms

Memory512MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a _zebra_, if it starts with a bad day, ends with a bad day, and good and bad days are alternating in it. Let us denote bad days as _0_ and good days as _1_. Then, for example, sequences of days _0_, _010_, _01010_ are zebras, while sequences _1_, _0110_, _0101_ are not. Oleg tells you the story of days he lived in chronological order in form of string consisting of _0_ and _1_. Now you are interested if it is possible to divide Oleg's life history into several **subsequences**, each of which is a zebra, and the way it can be done. Each day must belong to exactly one of the subsequences. For each of the subsequences, days forming it must be ordered chronologically. Note that subsequence does not have to be a group of consecutive days. ## Input In the only line of input data there is a non-empty string _s_ consisting of characters _0_ and _1_, which describes the history of Oleg's life. Its length (denoted as |_s_|) does not exceed 200 000 characters. ## Output If there is a way to divide history into zebra subsequences, in the first line of output you should print an integer _k_ (1 ≤ _k_ ≤ |_s_|), the resulting number of subsequences. In the _i_\-th of following _k_ lines first print the integer _l__i_ (1 ≤ _l__i_ ≤ |_s_|), which is the length of the _i_\-th subsequence, and then _l__i_ indices of days forming the subsequence. Indices must follow in ascending order. Days are numbered starting from 1. Each index from 1 to _n_ must belong to exactly one subsequence. If there is no way to divide day history into zebra subsequences, print _\-1_. Subsequences may be printed in any order. If there are several solutions, you may print any of them. You do not have to minimize nor maximize the value of _k_. [samples]

Oleg 记录了他生活每一天的历史。对于每一天，他决定它是好的还是坏的。Oleg 将一个非空的天数序列称为 _zebra_，当且仅当它以坏天开始，以坏天结束，并且好天和坏天在其中交替出现。我们用 _0_ 表示坏天，用 _1_ 表示好天。例如，序列 _0_、_010_、_01010_ 是 zebra，而序列 _1_、_0110_、_0101_ 则不是。 Oleg 按时间顺序告诉你他生活的历史，以由 _0_ 和 _1_ 组成的字符串形式给出。现在你需要判断是否可以将 Oleg 的历史划分为若干个 *子序列*，每个子序列都是一个 zebra，并给出一种划分方式。每一天必须恰好属于一个子序列。对于每个子序列，其中的天数必须按时间顺序排列。注意，子序列不一定是连续的天数。输入数据仅有一行，包含一个非空字符串 #cf_span[s]，由字符 _0_ 和 _1_ 组成，描述了 Oleg 的生活历史。其长度（记为 #cf_span[|s|]）不超过 #cf_span[200 000] 个字符。如果存在一种将历史划分为 zebra 子序列的方法，则在输出的第一行打印一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ |s|]），表示最终的子序列数量。在接下来的 #cf_span[k] 行中，第 #cf_span[i] 行首先打印一个整数 #cf_span[li]（#cf_span[1 ≤ li ≤ |s|]），表示第 #cf_span[i] 个子序列的长度，然后打印 #cf_span[li] 个形成该子序列的天数的索引。索引必须按升序排列。天数从 1 开始编号。每个从 #cf_span[1] 到 #cf_span[n] 的索引必须恰好属于一个子序列。如果无法将历史划分为 zebra 子序列，则输出 _-1_。子序列的输出顺序可以任意。如果有多个解，你可以输出任意一个。你无需最小化或最大化 #cf_span[k] 的值。 ## Input 在输入的唯一一行中，有一个非空字符串 #cf_span[s]，由字符 _0_ 和 _1_ 组成，描述了 Oleg 的生活历史。其长度（记为 #cf_span[|s|]）不超过 #cf_span[200 000] 个字符。 ## Output 如果存在一种将历史划分为 zebra 子序列的方法，则在输出的第一行打印一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ |s|]），表示最终的子序列数量。在接下来的 #cf_span[k] 行中，第 #cf_span[i] 行首先打印一个整数 #cf_span[li]（#cf_span[1 ≤ li ≤ |s|]），表示第 #cf_span[i] 个子序列的长度，然后打印 #cf_span[li] 个形成该子序列的天数的索引。索引必须按升序排列。天数从 1 开始编号。每个从 #cf_span[1] 到 #cf_span[n] 的索引必须恰好属于一个子序列。如果无法将历史划分为 zebra 子序列，则输出 _-1_。子序列的输出顺序可以任意。如果有多个解，你可以输出任意一个。你无需最小化或最大化 #cf_span[k] 的值。 [samples]

**Definitions** Let $ s = s_1 s_2 \dots s_n $ be a string of length $ n \geq 1 $, where $ s_i \in \{0,1\} $ for all $ i \in \{1, \dots, n\} $. A *zebra* is a non-empty subsequence $ s_{i_1}, s_{i_2}, \dots, s_{i_\ell} $ with $ 1 \leq i_1 < i_2 < \dots < i_\ell \leq n $ such that: - $ s_{i_1} = 0 $, - $ s_{i_\ell} = 0 $, - $ s_{i_j} \neq s_{i_{j+1}} $ for all $ j \in \{1, \dots, \ell-1\} $ (alternating 0 and 1). **Constraints** 1. $ 1 \leq n \leq 200{,}000 $ 2. Each day (index) $ i \in \{1, \dots, n\} $ must belong to exactly one zebra subsequence. 3. Each zebra subsequence must satisfy the alternating 0-1 pattern starting and ending with 0. **Objective** Determine if there exists a partition of $ \{1, 2, \dots, n\} $ into $ k \geq 1 $ disjoint zebra subsequences. If yes: - Output $ k $, the number of subsequences. - For each subsequence $ j \in \{1, \dots, k\} $, output $ \ell_j $ (its length) followed by the strictly increasing sequence of indices forming it. If no: output $-1$.

Samples

Input #1

Output #1

Input #2

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "A. Zebras",
    "description": {
      "content": "Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a _zebra_, if it starts with a bad day, ends with a bad day, a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF949A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Oleg writes down the history of the days he lived. For each day he decides if it was good or bad. Oleg calls a non-empty sequence of days a _zebra_, if it starts with a bad day, ends with a bad day, a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Oleg 记录了他生活每一天的历史。对于每一天，他决定它是好的还是坏的。Oleg 将一个非空的天数序列称为 _zebra_，当且仅当它以坏天开始，以坏天结束，并且好天和坏天在其中交替出现。我们用 _0_ 表示坏天，用 _1_ 表示好天。例如，序列 _0_、_010_、_01010_ 是 zebra，而序列 _1_、_0110_、_0101_ 则不是。\n\nOleg 按时间顺序告诉你他生活的历史，以由...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n \\geq 1 $, where $ s_i \\in \\{0,1\\} $ for all $ i \\in \\{1, \\dots, n\\} $.  \nA *zebra* is a non-empty subsequence $ s_{i_1}, s_{i_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments