#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int e[N] = {0, 0, 2, 7, 6, 5, 2, 7, 6, 5}, idx = 10, size = 8;
int l[N] = {0, 9, 0, 2, 3, 4, 5, 6, 7, 8};
int r[N] = {2, 0, 3, 4, 5, 6, 7, 8, 9, 1};
void print() {
for (int i = r[0]; i != 1; i = r[i]) {
cout << e[i] << " ";
}
cout << endl;
}
void add(int k, int x) { // 在k的后面插入x
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main() {
cout << "原来的数据: " << endl;
print();
// 1.名字有几个字, 就把前面几个字, 放到后面, 这里是3个字为例
int n = 3;
for (int i = 0; i < n; i++) {
add(l[1], e[r[0]]);
remove(r[0]);
}
cout << "名字的3张放到后面之后: " << endl;
print();
// 2.把上面的三张插到剩下元素的中间
int mid = idx - 1 + r[0] + 3 >> 1;
n = 3;
for (int i = 0; i < n; i++) {
add(l[mid], e[r[0]]);
remove(r[0]);
}
cout << "上面三张插入中间之后: " << endl;
print();
// 3.秘密的第一个存在res中, 元素少一个
int res = r[0];
remove(r[0]);
cout << "藏起来一个之后: " << endl;
print();
size--;
// 4.南方人拿一张, 北方人拿两张, 不确定拿三张, 插到中间去
n = 2;
for (int i = 0; i < n; i++) {
add(l[mid], e[r[0]]);
remove(r[0]);
}
cout << "地区拿n张插入中间之后: " << endl;
print();
// 5.男生一张扔出去, 女生两张扔出去
n = 1;
for (int i = 0; i < n; i++) {
remove(r[0]);
size--;
}
cout << "性别扔出去之后: " << endl;
print();
// 6.见证奇迹的时刻, 7个字放到最后
n = 7;
for (int i = 0; i < n; i++) {
add(l[1], e[r[0]]);
remove(r[0]);
}
cout << "见证奇迹的时刻放到后面之后: " << endl;
print();
// 7.好运留下来, 烦恼丢出去, 第一张放到最后, 第二张丢出去
while (size > 1) {
add(l[1], e[r[0]]);
remove(r[0]);
remove(r[0]);
size--;
}
cout << "好运留下来, 烦恼丢出去之后: " << endl;
print();
return 0;
}