Input format

Output format

Meaning translation
Initially, there are from left to right n n n wooden blocks numbered 0 ... n − 1 0 \ldots n-1 0... n − 1, the following four operations are required:

• move a onto b: put the wood block above a and b in place, and then put a on b.
• move a over b: return the wood block above a, and then put a on the top of the pile of wood blocks where b is located.
• pile a onto b: put the wood blocks above b in place, and then lump the wood blocks above a onto b.
• pile a over b: lump the wood blocks of a and above onto b.
• The end flag of a group of data is quit. If there are illegal instructions (for example, a and b are in the same pile), it does not need to be processed.

Output: after all operations are input, the wood block number of each position is output from left to right and from bottom to top.

Sample input and output
Enter #1

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

Output #1

0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

Solution simulation

The meaning of this topic is a little complicated, but it's not difficult to understand. If you write a function for each of the four operations and solve the problem violently, it is actually feasible. However, through observation, we abstract two common operations - homing and moving, and then implement four instructions. The code is as follows. pos[maxn][2] is used to record the current pile position of the wood block and the position of the wood block in the pile, which is convenient to find.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 30;
int n, a, b, pos[maxn][2]; //pos[i][0] records the stacking position of wood block I, and pos[i][1] records the position of wood block I in the stacking pos[i][0] 
char act[5], how[5];
vector<int> blcs[maxn]; //blocks
void blocksReturn(int x) { //The homing function returns all the wood blocks above X in the pile where x is located to its original position 
	int blcPos = pos[x][0];
	for (int i = blcs[blcPos].size() - 1; blcs[blcPos][i] != x; --i) { //The position of the wooden block x in the pile can be used here 
		int val = blcs[blcPos].back(); 
		blcs[blcPos].pop_back();
		pos[val][0] = val, pos[val][1] = blcs[val].size(); //Put it back in the original heap 
		blcs[val].push_back(val);
	}
} 
void putOn(int x, int y) { //Put X and the wood blocks above x (if any) in the pile where x is located on the pile where y is located as a whole 
	int xBlcPos = pos[x][0], yBlcPos = pos[y][0], xPos = pos[x][1]; //Query the heap position of x and the position of x in the heap 
	for (int i = xPos; i < blcs[xBlcPos].size(); ++i) {
		int val = blcs[xBlcPos][i];
		pos[val][0] = yBlcPos, pos[val][1] = blcs[yBlcPos].size();
		blcs[yBlcPos].push_back(val); //Put it on the pile of wooden blocks where y is located
	}
	while (blcs[xBlcPos].size() > xPos) blcs[xBlcPos].pop_back(); //Really discard elements 
} 
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) { blcs[i].push_back(i); pos[i][0] = i, pos[i][1] = 0; }
	while (~scanf("%s", act)) {
		if (strcmp(act, "quit") == 0) break;
		scanf("%d %s %d", &a, how, &b);
		if (a == b || pos[a][0] == pos[b][0]) continue; //Illegal instruction 
		if (strcmp(act, "move") == 0) { 
			if (strcmp(how, "onto") == 0) { //move a onto b
				blocksReturn(a), blocksReturn(b); //Put all the wood blocks above a and b in place
				putOn(a, b); //At this time, both a and b are at the top of their respective wood blocks; Put a on b 
			} else { //move a over b
				blocksReturn(a); //Put the wood block above a in place
				putOn(a, b); //At this time, a is at the top of the pile of wood blocks; Put a on the top of the pile of wood blocks where b is located 
			}
		} else if (strcmp(act, "pile") == 0) {
			if (strcmp(how, "onto") == 0) { //pile a onto b
				blocksReturn(b); //Put the wood block above b in place
				putOn(a, b); //At this time b, it is at the top of the pile of wood blocks; Put a and the wood block above it on b 
			} else { //pile a over b
				putOn(a, b); //Put the wood blocks above a on the top of the pile of wood blocks where b is located 
			}
		} 
	}  
	for (int i = 0; i < n; ++i) {
		printf("%d:", i);
		for (int j = 0; j < blcs[i].size(); ++j) printf(" %d", blcs[i][j]);
		printf("\n");
	}
	return 0;
} 

At this time, the code can be AC:

However, there is room for further simplification. For example, when implementing the four instructions with homing and moving, it is found that the wood block above a must be homing when there is move, and the wood block above b must be homing when there is onto. Therefore, the simplified main() function is as follows, just like other codes:

//......
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) { blcs[i].push_back(i); pos[i][0] = i, pos[i][1] = 0; }
	while (~scanf("%s", act)) {
		if (strcmp(act, "quit") == 0) break;
		scanf("%d %s %d", &a, how, &b);
		if (a == b || pos[a][0] == pos[b][0]) continue; //Illegal instruction 
		if (strcmp(act, "move") == 0) blocksReturn(a); //Put the wood block above a in place
		if (strcmp(how, "onto") == 0) blocksReturn(b); //Put the wood block above b in place 
		putOn(a, b); //Put the wood blocks above a on the top of the pile of wood blocks where b is located 
	}  
	for (int i = 0; i < n; ++i) {
		printf("%d:", i);
		for (int j = 0; j < blcs[i].size(); ++j) printf(" %d", blcs[i][j]);
		printf("\n");
	}
	return 0;
} 

If you use a linked list (such as a static linked list), the efficiency of the putOn() function can be further improved. Whether you are handling a block or a pile of blocks, the time complexity can be achieved O ( 1 ) O(1) O(1) .