| ENG RUS | Timus Online Judge |
[Online] ICPC Ural Regional Contest Qualifier 2026
Contest is over
I. Binary Sort 2Time limit: 5.0 second Memory limit: 256 MB Timofey completed a course on algorithms and studied many different types of sorting. He still encounters new and unusual sorting algorithms. Every time Timofey learns a new sorting algorithm, he needs to practice on a binary string. Usually, during practice, he chooses a sequence of substrings and sorts them one by one, but sometimes this sequence turns out to be very large, and Timofey cannot practice on long strings. Timofey decided to speed up this process by performing some operations in parallel and learned about the following sorting method. It uses a system of N parallel pipelines of length M, numbered from top to bottom from 1 to N, with one bit fed into each of them.
The pipelines are denoted by the = symbols, and the jumpers connecting adjacent pipelines are denoted by the | symbols. Two jumpers touching the same pipeline cannot be in the same column. All N bits move simultaneously along the pipelines from left to right at the same speed. When the bits reach a jumper, it sorts them. That is, the smaller bit goes to the upper pipeline, and the larger one — to the lower one. For example:
The system takes a binary string of length N, where the i-th bit is fed into the i-th pipeline. The bits travel to the end of the pipelines, after which a binary string of length N is also obtained. Timofey has Q binary strings of length N on which he was going to practice. Help determine for each string what string will be obtained at the output of the system. InputThe first line contains three integers N, M, Q (1 ≤ N, M, Q ≤ 3000) — the number of pipelines, the length of the pipelines, and the number of Timofey’s binary strings. From the second to the 2 · N-th line of the input data, the pipeline system is given. The even-numbered lines contain the pipelines, each consisting of M = characters, and the odd-numbered lines consist of M | characters and spaces. In a single column, there are no two jumpers touching the same pipeline.The following Q lines contain binary strings of length N that Timofey wants to pass through the system. OutputOutput Q binary strings obtained after passing through the system. Samples
Problem Author: Timofey Imaev Problem Source: The 2026 ICPC Ural Qualification |