Ponderous Pondering Ducks
Output: Standard Output (stdout)
Memory limit: 255 megabytes
Time limit: 1.2 seconds
After being freed from Thomas's grasp, the group of ducks want to swim to their favourite spots in a rectangular pond. They are orderly ducks, and so they wait while each swims out to their favourite spot one by one. The ducks enter the pond at the bottom left corner, and swim only directly rightwards or upwards (for orderliness' sake). The ducks each inform you (a widely trusted individual in duck communities) of their intended route to reach their favourite spot. However, the ducks are both terrible at planning and incredibly stubborn, and so their routes may pass through spots where ducks are already positioned. Rather than changing their routes, they plough on regardless and simply crash into the ducks along their way. Though this crash causes much disgruntlement, the duck crashed into will still remain in the same position, and the duck currently moving will still continue its route as planned. Additionally, if the destination spot of a duck is already occupied, the ducks will begrudgingly share the spot, though this will count as a collision. If a duck does not move (ie. it stays at (0, 0)) then every subsequent duck will collide with that duck.
Your task is to determine, for each duck, whether it will crash into one or more ducks along its route. (Perhaps if you present your conclusions persuasively enough, their orderliness will overcome their stubborness and they will rethink their routes.)
The first line contains integers H and W, the height and width of the pond. The pond is divided into H \times W squares, and each duck begins their route in the bottom left square (0, 0).
The second line contains the integer N, the number of ducks.
Each of the next N lines contains the planned route of each duck in the order in which they enter the pond. Every line contains space-seperated integers in the following format:
The first integer is m_i. This is followed by 2 \times m_i non-negative integers, each representing the distance of one leg of the duck's route. The legs alternate between upwards legs and rightwards legs. For example, the line '2 1 2 3 4' represents a route with 2 \times 2=4 legs, with the legs going 1 up, 2 right, 3 up, then 4 right.
You should output N lines. For each duck, in the order in which they enter the pond:
- If the duck's route does not collide with the already positioned ducks, output
"smooth swimming"on a single line.
- Otherwise, output
"OUCH"on a single line.
For all subtasks:
- 1 \le H, W \le 1,000,000,000
- 1 \le N \le 10000
- 1 \le m_i \le 100
- It is guaranteed that no duck's route will take it outside of the pond.
- Subtask 1 (+25%): H, W, N \le 1000
- Subtask 2 (+25%): H = 1
- Subtask 3 (+25%): N \le 100
- Subtask 4 (+25%): no further constraints
Warning: Subtasks 2 and 4 contain cases with very large amounts of input data. If you believe you have a fast enough algorithm, but are still receiving Time Limit Exceeded verdicts in subtask 2 or 4, this might be due to slow I/O performance – see this document for tips on how to improve this.
Additionally, it is possible that Python submissions with a correct algorithm may still time out, even when submitted with PyPy. If you think this might be the case, please contact us at email@example.com and we will review your submission manually.
Sample Input 1
7 7 3 1 4 4 1 1 1 2 0 4 6 0
Sample Output 1
smooth swimming smooth swimming OUCH