思路与算法

建n个点，每个u有两条编号2u、2u+1的有向边，边终点为编号模n。迭代Hierholzer求欧拉回路，按边编号输出就是2n个人的座次。

正确性说明

每点入度出度均2。走k步可到(2^k u+r) mod n，0≤r<2^k，足够大k可覆盖所有点，所以强连通并有欧拉回路。连续两条边a,b满足floor(b/2)=a mod n，即b是2a或2a+1模2n，闭合也成立；每条边使用一次保证每个人恰好一次。

复杂度

每组初始化O(n)，每条边入栈出栈一次，总O(n)时间与O(n)空间；多组逐组输出。

易错点

有多种合法座次，不能与唯一文本答案比较。特判完整检查编号范围、无重复及包含末尾到开头的后继条件。本批另用反向选边的合法程序和全零非法程序作原生探针。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector<int> used(n), v(1, 0), es, ans;
        ans.reserve(2 * n);
        while (!v.empty()) {
            int u = v.back();
            if (used[u] < 2) {
                int e = 2 * u + used[u]++;
                v.push_back(e % n);
                es.push_back(e);
            } else {
                v.pop_back();
                if (!es.empty()) {
                    ans.push_back(es.back());
                    es.pop_back();
                }
            }
        }
        reverse(ans.begin(), ans.end());
        for (int i = 0; i < 2 * n; i++)
            cout << ans[i] << (i + 1 == 2 * n ? '\n' : ' ');
    }
}