# F. Gravity Falls [문제 링크](https://codeforces.com/contest/2148/problem/F) ## Problem Statement Farmer John has $n$ arrays $a_1, a_2, \ldots, a_n$ 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 \leq t \leq 1000$) — the number of test cases. The first line of each test case contains $n$ ($1 \leq n \leq 2 \cdot 10^5$). For the following $n$ lines, the first integer $k_i$ ($1 \leq k \leq 2 \cdot 10^5$) denotes the length of $a_i$. Then, $k_i$ space-separated integers $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ follow ($1 \leq a_{i_j} \leq 2 \cdot 10^5$). It is guaranteed that the sum of $n$ and the sum of all $k_i$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output the lexicographically minimum bottom row on a new line. ## 풀이 출력해야 하는 인덱스마다 해당 인덱스부터 비교했을 때, 가장 앞에 오는 블록을 찾아 먼저 출력하고 인덱스를 그 뒤로 이동시키며 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; bool comp(vector<int> &a, vector<int> &b, int startIdx) { if(a.size()<=startIdx) return true; if(b.size()<=startIdx) return false; for(int i=startIdx;i<a.size() && i<b.size();i++) { if(a[i]!=b[i]) return a[i] > b[i]; } return a.size()>b.size(); } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; int maxLen=0; vector<vector<int>> grid(n); for(int i=0;i<n;i++) { int k; cin >> k; maxLen = max(maxLen, k); while(k--) { int a; cin >> a; grid[i].push_back(a); } } for(int i=0;i<maxLen;) { int maxIdx=0; for(int j=1;j<n;j++) { if(comp(grid[maxIdx], grid[j], i)) maxIdx=j; } for(int j=i;j<grid[maxIdx].size();j++) cout << grid[maxIdx][j] << ' '; i = grid[maxIdx].size(); } cout << '\n'; } } ```