50095. Lines of Words

I'm a slow walker, but I never walk backwards.

Task Description

Given $N$ lines of words, switch words among them. We will use $(l, w)$ to indicate the $w_{th}$ word in the $l_{th}$ line. Both line and word numbers are from $0$. For the example $(0, 0)$ is apple, $(1, 0)$ is bird, and $(2, 2)$ is frog for the following input.

apple
bird cat
dog elephant frog

Now we will process requests for switching words. A request $(l_{1}, w_{1}, l_{2}, w_{2})$ indicates that we need to switch words $(l_{1}, w_{1})$ and $(l_{2}, w_{2})$. Note that we guarantee that the indices are all valid.

For example, if the request is $(0, 0, 2, 2)$, then we switch apple with frog, and the lines change as follow. After finishing processing requests, output the final result in a line by line manner.

frog
bird cat
dog elephant apple

Subtask

$N$ is the number of lines, $L_{i}$ is the number of words in the $i_{th}$ line, $L$ is the total number of words, $w$ is the max length of a word and $W$ is the total number of characters (including '\0') in all words.

  • 30 points: The input data is small.
    • $N \lt 32$
    • $L_{i} \lt 32$
    • $L \lt 1024$
    • $w \lt 32$
    • $W \lt 50000$
  • 40 points: $W$ is significantly large, so using "strcpy" function will cause TLE. Instead you should use a 2D pointer array, and switch the pointers only.
    • $N \lt 32$
    • $L_{i} \lt 32$
    • $L \lt 1024$
    • $w \lt 1024$
    • $W \lt 500000$
  • 30 points: $N$ and the the maximum number of words in a line are extremely large, so allocating a 2D pointer array will cause MLE. You should use “two-level pointer”, as in the task last week, to implement the line and word structure. Also the number of characters in a word could vary dramatically, so you need to put all of them in a one-dimensional array to save storage. That is, whenever you read a word you advance the pointer to the next available position in that array. This can also save storage.
    • $N \lt 1024$
    • $L_{i} \lt 1024$
    • $L \lt 16384$
    • $w \lt 1024$
    • $W \lt 10000000$
Subtask3 Tow Level Pointer

Input Format

The input contains only one test case. The first line contains one integer $N$, representing the number of lines. The next $N$ lines contains $L_{i}$ words. After $N+1$ lines, there is a line contains one integer $M$, representing the number of requests. The next $M$ lines contains four integers $l_{1}$, $w_{1}$, $l_{2}$, $w_{2}$.

Output Format

Print the $N$ lines in the table in each line, and each word in one line is separated by a single space. And a 'newline' after the last word in each line.

Sample Input 1

3
apple
bird cat
dog elephant frog
1
0 0 1 0

Sample Output 1

bird
apple cat
dog elephant frog

Sample Input 2

3
apple
bird cat
dog elephant frog
5
0 0 1 0
1 0 1 1
1 1 2 0
2 0 2 1
2 1 2 2

Sample Output 2

bird
cat dog
elephant frog apple

Discussion