Zebra

Đề bài

Mô tả

Oleg ghi lại lịch sử những ngày mình đã sống. Mỗi ngày được đánh dấu là ngày tốt (ký hiệu là 1) hoặc ngày xấu (ký hiệu là 0).

Một dãy các ngày không rỗng được gọi là một zebra nếu nó bắt đầu bằng một ngày xấu, kết thúc bằng một ngày xấu, và các ngày tốt, xấu xen kẽ nhau. Ví dụ, các dãy 0, 010, 01010 là zebra, còn 1, 0110, 0101 thì không.

Lịch sử của Oleg được cho dưới dạng một xâu s gồm các ký tự 01 theo thứ tự thời gian. Hãy chia lịch sử này thành một số dãy con, mỗi dãy con là một zebra. Mỗi ngày phải thuộc đúng một dãy con, và trong mỗi dãy con các ngày phải giữ nguyên thứ tự thời gian (dãy con không nhất thiết gồm các ngày liên tiếp).

Nếu có cách chia, hãy in ra một cách bất kỳ. Nếu không, in ra 1.

Dữ liệu vào

Một dòng duy nhất chứa xâu s không rỗng gồm các ký tự 01.

Dữ liệu ra

Nếu không thể chia, in ra 1.

Ngược lại, dòng đầu in số nguyên k (1k|s|), là số dãy con. Trong k dòng tiếp theo, dòng thứ i in số nguyên li (độ dài dãy con thứ i), tiếp theo là li chỉ số của các ngày tạo thành dãy con đó theo thứ tự tăng dần. Các ngày được đánh số bắt đầu từ 1.

Mỗi chỉ số từ 1 đến |s| phải xuất hiện đúng một lần. Các dãy con có thể in theo thứ tự bất kỳ. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1|s|200000
  • s chỉ gồm các ký tự 01

Ví dụ

Input Output Giải thích
0010100 3
1 1
5 2 3 4 5 6
1 7
Chia thành ba zebra: ngày (1) cho xâu 0, các ngày (2,3,4,5,6) cho xâu 01010, và ngày (7) cho xâu 0. Nhiều cách chia khác cũng được chấp nhận.
111 -1 Không ngày nào là ngày xấu nên không thể tạo bất kỳ zebra nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0