题解：CF2038I Polyathlon

不妨将举行第 i 个项目时的选手看成从第 i 列向后循环到第 i-1 列组成的 n 个长度 m 的串。

不难发现，第 i 列的获胜者即为这 n 个串中字典序最大的一个。

将第 n 位作为第 n 个关键字，第一位作为第 1 关键字，用 LSD 基数排序的思想计算出第 1 列所有选手的排名，然后我们考虑动态维护这个排名来计算剩余列的答案。

从第 i 列转移到第 i-1 列，每次相当于将串的最后一位移动到第一位并成为新的第 1 关键词，继续基数排序即可。

最终我们可以用 \mathcal O(nm) 的复杂度计算出第 1 列 的答案，再用 \mathcal O(nm) 的复杂度计算出剩余 m-1 列的答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, tot;
int a[N], b[N], ans[N];
vector<vector<int>> sq;
string s;
signed main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    sq.resize(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> s, sq[i].resize(m + 1), a[i] = i;
        for (int j = 1; j <= m; ++j)
            sq[i][j] = s[j - 1] - '0';
    }
    for (int i = m; i >= 1; --i)
    {
        tot = 0;
        for (int j = 1; j <= n; ++j)
            if (sq[a[j]][i])
                b[++tot] = a[j];
        for (int j = 1; j <= n; ++j)
            if (!sq[a[j]][i])
                b[++tot] = a[j];
        for (int j = 1; j <= n; ++j)
            a[j] = b[j];
    }
    ans[1] = a[1];
    for (int i = m; i >= 2; --i)
    {
        tot = 0;
        for (int j = 1; j <= n; ++j)
            if (sq[a[j]][i])
                b[++tot] = a[j];
        for (int j = 1; j <= n; ++j)
            if (!sq[a[j]][i])
                b[++tot] = a[j];
        for (int j = 1; j <= n; ++j)
            a[j] = b[j];
        ans[i] = a[1];
    }
    for (int i = 1; i <= m; ++i)
        cout << ans[i] << " ";
    return 0;
}