更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19361912

大意

有 $n+1$ 根柱子（编号 $1 \sim n+1$），其中 $1 \sim n$ 号柱子初始时各有 $m$ 个球（球按**自底向上**的顺序摆放），$n+1$ 号柱子初始为空；所有球共包含 $n$ 种颜色，且每种颜色的球恰好有 $m$ 个。

允许执行的操作是：将某根柱子最上方的球移动到另一根柱子的最上方，操作需满足两个条件：

1. 源柱子（移出球的柱子）非空；

2. 目标柱子（移入球的柱子）上的球数量不超过 $m-1$。

要求通过不超过 $820000$ 次上述操作，使得所有同一种颜色的球都汇聚到同一根柱子上（每种颜色最终对应哪根柱子无限制）。

思路

首先，这个题是个构造题，然后我们考虑构造方法，先看特殊性质 $n = 2$ 的时候，也就是说此时只有 $3$ 个柱子和 $2$ 种颜色，那么我们应该怎么去放这个东西呢？

我们将两种颜色用白和黑表示，那么我们很容易想到去分离黑白，如何做呢？如上图，我们先在第二个柱子上空出第一个柱子中黑的个数，这样就可以将第一根柱子黑白分离，再把分离好的放回去，把剩下的没分的整到一根柱子上，再把第一根的黑白分离到两个不同的柱子上，然后把没分离的那根柱子直接按黑白分离即可。

总操作次数是：$5m - k$，$k$ 表示第一个柱子中黑的个数。

我们继续考虑 $n$ 比较大的时候怎么办，我们可以像刚刚的操作一样，对于每一个颜色 $i \in [1, n]$ 依次操作，对于颜色 $i$，先把 $[i + 1, n]$ 的柱子中的颜色 $i$ 全放在柱头，然后直接如下图进行操作即可：

但是经过计算发现以上的构造方式并不能通过本题，我们需要考虑其他的方法。

考虑分治。

我们发现对于 $n  = 2$ 的情况处理起来很容易，要是全部都能当成两个颜色做就好了，于是我们就可以对于当前处理的区间 $[l, r]$ 进行分治 $[l, mid], [mid + 1, r]$，我们将 $[l, mid]$ 的柱子全部整理成颜色小于等于 mid 的，将 $[mid + 1, r]$ 的柱子全部整理成颜色大于 mid 的，每次分治时，可以 $\mathcal{O}(n ^ 2)$ 的去枚举 $i \in [l, mid], r \in [mid + 1, r]$，对 $i$ 和 $j$ 的颜色整理。如果两个柱子中颜色小于等于 mid 的大于 $m$，就将 $i$ 整理，反之。

因此就解决了这道题。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 16005;
int n, m;
vector<int> g[MAXN];
bool vis[MAXN];
int S[MAXN], c = 0;

inline int get_id(int x) {
    x--;
    return x;
}

bool dfs(int u) {
    if (vis[u ^ 1]) return false;
    if (vis[u]) return true;
    vis[u] = true;
    S[c++] = u;
    for (int v : g[u]) {
        if (!dfs(v)) return false;
    }
    return true;
}

bool Two_SAT() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            c = 0;
            if (!dfs(i)) {
                while (c > 0) vis[S[--c]] = false;
                if (!dfs(i + 1)) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        int u = get_id(a);
        int v = get_id(b);
        g[u].push_back(v ^ 1);
        g[v].push_back(u ^ 1);
    }

    if (!Two_SAT()) {
        cout << "NIE" << endl;
    } else {
        vector<int> ans;
        for (int i = 0; i < 2 * n; i += 2) {
            if (vis[i]) {
                ans.push_back(i + 1);
            } else {
                ans.push_back(i + 2);
            }
        }
        sort(ans.begin(), ans.end());
        for (int x : ans) {
            cout << x << endl;
        }
    }

    return 0;
}