蓝桥杯 自行车停放 双向链表

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 200010;
 4 int e[N], l[N], r[N], idx;
 5 int e_idx[N]; //e_idx(x) = idx;即表示值为x的节点的下标是idx 
 6 void init() {
 7     r[0] = 1;
 8     l[1] = 0;
 9     idx = 2;
10 }
11 void add(int k, int x) {
12     e[idx] = x;
13     e_idx[x] = idx;
14     r[idx] = r[k];
15     l[idx] = k;
16     l[r[k]] = idx;
17     r[k] = idx;
18     //cout << "e:" << x << " " << "idx:" << idx << endl;
19     idx++;
20 }
21 int main() {
22     int n;
23     cin >> n;
24     init();
25     int a;
26     cin >> a;
27     add(0, a);
28     n--;
29     /*cout << "结果为：";
30     for (int i = r[0]; i != 1; i = r[i]) {
31         cout << e[i] << " ";
32     }
33     cout << endl;*/
34     while (n--) {
35         int x, y, z;
36         cin >> x >> y >> z;
37         if (z == 0) { //左边插入 
38             add(l[e_idx[y]], x);
39         } else { //右边插入 
40             add(e_idx[y], x);
41         }
42         /*cout << "结果为：";
43         for (int i = r[0]; i != 1; i = r[i]) {
44             cout << e[i] << " ";
45         }
46         cout << endl;*/
47     }
48     for (int i = r[0]; i != 1; i = r[i]) {
49         cout << e[i] << " ";
50     }
51     return 0;
52 }