C. Zebras

Codeforces

IDCF950C

Time1000ms

Memory512MB

Difficulty—

constructive algorithmsgreedy

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 \in \{0,1\}^n $ be a binary string of length $ n \geq 1 $, where $ 0 $ denotes a bad day and $ 1 $ denotes a good day. A *zebra* is a non-empty subsequence $ (i_1, i_2, \dots, i_\ell) $ with $ 1 \leq i_1 < i_2 < \dots < i_\ell \leq n $ such that: - $ s[i_1] = 0 $, - $ s[i_\ell] = 0 $, - For all $ j \in \{1, \dots, \ell-1\} $, $ s[i_j] \ne s[i_{j+1}] $ (alternating). **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 condition starting and ending with 0. **Objective** Partition the indices $ \{1, \dots, n\} $ into $ k \geq 1 $ disjoint zebra subsequences, or determine that no such partition exists. If possible: - Output $ k $, the number of subsequences. - For each subsequence $ j \in \{1, \dots, k\} $, output $ \ell_j $ followed by the $ \ell_j $ indices (in increasing order) forming the subsequence. If impossible: output $ -1 $.

Samples

Input #1

Output #1

Input #2

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. 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": "CF950C"
  },
  "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 \\in \\{0,1\\}^n $ be a binary string of length $ n \\geq 1 $, where $ 0 $ denotes a bad day and $ 1 $ denotes a good day.  \n\nA *zebra* is a non-empty subsequence $ (i_1, i_2, \\d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments