Gravity Falls

[]

题目描述

F. Gravity Falls

time limit per test
2 seconds
memory limit per test
256 megabytes

Farmer John has n
arrays a1,a2,…,an that may have different lengths. He will stack the arrays on top of each other, resulting in a grid with n rows. The arrays are left-aligned and can be stacked in any order he desires.

Then, gravity will take place. Any cell that is not on the bottom row and does not have an element beneath it will fall down a row. This process will be repeated until there are no cells that satisfy the aforementioned constraint.

Over all possible ways FJ can stack the arrays, output the lexicographically minimum bottom row after gravity takes place.

Input

The first line contains t (1≤t≤1000) — the number of test cases.

The first line of each test case contains n (1≤n≤2⋅105).

For the following n lines, the first integer ki (1≤k≤2⋅105) denotes the length of ai.

Then, ki space-separated integers ai1,ai2,…,aiki follow (1≤aij≤2⋅105).

It is guaranteed that the sum of n and the sum of all ki over all test cases does not exceed 2⋅105.

Output

For each test case, output the lexicographically minimum bottom row on a new line.

img

思路

Greedy + sort

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;

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

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n; 
        cin >> n;
        vector<vector<int>> a(n);
        int L = 0; // 最大长度
        for (int i = 0; i < n; ++i) {
            int k; 
            cin >> k;
            a[i].resize(k);
            for (int j = 0; j < k; ++j) cin >> a[i][j];
            L = max(L, k);
        }

        // parts[j]: 能到达第 j 列的行
        vector<vector<int>> parts(L);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < (int)a[i].size(); ++j)
                parts[j].push_back(i);

        // ranks[i][j]: 第 i 行从 j 开始后缀的名次；越界 ranks[i][len]=0
        vector<vector<int>> ranks(n);
        for (int i = 0; i < n; ++i)
            ranks[i].assign((int)a[i].size() + 1, 0);

        // order[j]: 第 j 列按 (a[i][j], ranks[i][j+1]) 从小到大排序后的行号
        vector<vector<int>> order(L);

        // 自右向左求 rank
        for (int j = L - 1; j >= 0; --j) {
            struct Node { int val, nxt, id; };
            vector<Node> v; v.reserve(parts[j].size());
            for (int i : parts[j]) {
                int nxtRank = ranks[i][j + 1]; // 越界即 0
                v.push_back({a[i][j], nxtRank, i});
            }
            sort(v.begin(), v.end(), [](const Node& x, const Node& y){
                if (x.val != y.val) return x.val < y.val;
                return x.nxt < y.nxt; // 值相同则谁的“下一段”更小谁更优；越界(0)最小
            });
            order[j].reserve(v.size());
            int curRank = 0;
            int pv = INT_MIN, pn = -1;
            for (auto &nd : v) {
                if (nd.val != pv || nd.nxt != pn) {
                    ++curRank;
                    pv = nd.val; pn = nd.nxt;
                }
                ranks[nd.id][j] = curRank;
                order[j].push_back(nd.id);
            }
        }

        // 生成答案
        vector<char> used(n, 0);
        vector<int> ptr(L, 0); // 每列 order 的游标
        int cur = -1;
        for (int j = 0; j < L; ++j) {
            if (cur != -1 && (int)a[cur].size() > j) {
                cout << a[cur][j] << (j + 1 == L ? '\n' : ' ');
                continue;
            }
            // 需要换人：在当前列选后缀最小、且未使用的行
            auto &ord = order[j];
            while (ptr[j] < (int)ord.size() && used[ord[ptr[j]]]) ++ptr[j];
            int i = ord[ptr[j]++]; // 必存在
            used[i] = 1;
            cur = i;
            cout << a[cur][j] << (j + 1 == L ? '\n' : ' ');
        }
    }
    return 0;
}