知识点:静态链表
需要注意的地方,可能整个链表里面的值都不同,也就是第二个-1不需要输出,所以程序里面加了一行return,就是因为这个原因,测试点2就是这个点
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;
const int N = 1e5 + 5;
struct node {
int address, key, nxt, flag;
node(int a = 0, int b = 0, int c = 0, int d = N * 2): address(a), key(b), nxt(c), flag(d) {}
} List[N];
int Hash[N];
bool cmp(node a, node b) {
return a.flag < b.flag;
}
int main() {
int s, n; cin >> s >> n;
for (int i = 0; i < n; i++) {
int a, b, c; cin >> a >> b >> c;
List[a] = node(a, b, c, N * 2);
}
int p = s, cnt1 = 0, cnt2 = 0;
while (p != -1) {
if (Hash[abs(List[p].key)]) List[p].flag = N + cnt2++;
else { Hash[abs(List[p].key)] = 1; List[p].flag = cnt1++; }
p = List[p].nxt;
}
sort(List, List + N, cmp);
for (int i = 0; i < cnt1 - 1; i++) printf("%05d %d %05d\n", List[i].address, List[i].key, List[i + 1].address);
printf("%05d %d -1\n", List[cnt1 - 1].address, List[cnt1 - 1].key);
if (cnt2 == 0) return 0;
for (int i = cnt1; i < cnt1 + cnt2 - 1; i++) printf("%05d %d %05d\n", List[i].address, List[i].key, List[i + 1].address);
printf("%05d %d -1\n", List[cnt1 + cnt2 - 1].address, List[cnt1 + cnt2 - 1].key);
return 0;
}