https://codeforces.com/contest/2060/problem/B
题目大意
给出 $n$ 个长为 $m$ 的数组，这些数组中的元素为 $[0, nm - 1]$，每个各出现一次。
问是否存在 $n$ 长的排列 $p$ 使得，依次从 $p_1, p_2, p_3 …$ 数组中取出比刚才大的数，重复直到任一数组无法取出元素。使得最终取出的序列为 $[0, nm - 1]$ 的排列。
其中 $1 \le nm \le 2000$。
简要题解
题目写的花里胡哨的，但因为要取出所有的元素，实际上就是说要按照 $p$ 的顺序能取完整的 $m$ 次。而至少第一列的元素（每个数组开头的元素）要按照 $p$ 的顺序取，因此我们直接按照第一列的大小关系得出 $p$ 即可。
复杂度
$T$：$O(nm \log m)$
$S$：$O(nm)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, m; cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < n; i++) {
sort(a[i].begin(), a[i].end());
}
vector<int> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int x, int y){
return a[x][0] < a[y][0];
});
vector<int> res;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res.push_back(a[id[j]][i]);
}
}
// for (int i : id) cerr << i << ' ';
// cerr << endl;
// for (int i : res) cerr << i << ' ';
// cerr << endl;
for (int i = 1; i < n * m; i++) {
if (res[i - 1] > res[i]) {
cout << "-1\n";
return;
}
}
for (int i = 0; i < n; i++) {
cout << (id[i] + 1) << (" \n"[i == n - 1]);
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Game of Mathletes - Codeforces Round 998 (Div. 3)