Algo lab/zooma 1
Zooma 1
This task is motivated by Zuma, a video game by PopCap Games.
In this version of the game, there is a sequence of n colored balls that moves toward an exit. You can shoot another m colored balls into the sequence. Balls do not disappear in this version.
Find out the final sequence of the balls.
The balls in the original sequence are numbered from 1 to n. The balls that you shoot are numbered from n+1 to n+m.
Game play example
Consider the case where n=5 and m=4.
The original sequence has balls with these colors:
1 2 3 4 5 G B G Y Y
You have 4 balls numbered as this:
6 7 8 9 R G B G
If you shoot your first ball to the location after ball 3, the sequence becomes
1 2 3 *6* 4 5 G B G *R* Y Y
If you shoot your second ball to the location after ball 1, the sequence becomes
1 *7* 2 3 6 4 5 G *G* B G R Y Y
If you shoot your third ball to the location after ball 6, the sequence becomes
1 7 2 3 6 *8* 4 5 G G B G R *B* Y Y
If you shoot your forth ball to the location after ball 5, the sequence becomes
1 7 2 3 6 8 4 5 *9* G G B G R B Y Y *G*
and this is the final sequence.
Note: In this version, the colors of the balls are not relevant because balls do not disappear.
Input
- First line: n and m (n <= 1,000,000; m <= 1,000,000)
- Notes: in the grader n <= 100,000; m <= 100,000. Time limit 1 second (easy), 3 second (hard)
- Next n lines: for 1≤i≤n, line 1+i specifies one integer c[i] the color of ball i.
- Next m lines: for 1≤j≤m, line 1+n+j specifies two integers d[j] and p[j]. d[j] is the color of ball n+j (this is your j-th ball), and p[j] is the number of the ball right after which you shoot this ball into the sequence. Note that p[j] < n+j.
Output
Your program should print n+m integers which are the ball numbers in the final sequence.
Example
This is the same example with colors: G = 1, B = 2, Y = 3, R = 4.
Input
5 4 1 2 1 3 3 4 3 1 1 2 6 1 5
Output
1 7 2 3 6 8 4 5 9
Test data
Download at: http://theory.cpe.ku.ac.th/~jittat/courses/01204212/tasks/zooma1/
Expected output for n10-3.in:
1 2 14 18 20 3 11 13 4 5 17 6 7 8 15 12 19 9 10 16
Expected output for n50-3.in (first 10 lines):
1 61 2 97 52 3 81 4 71 67 5
Code templates
Download here: [1]