---
tags: 卓越盃程式競賽
---

# pC. Safe Sorter

## 題目敘述 :

我們的保險箱現在要放到一個分類器之中，此分類器有許多節點(如下圖)，放入的規則如下。

<img src="https://live.staticflickr.com/65535/51821755725_f3cbcbed1f_o.png" width="714" height="579" alt="pic">

- 如果該節點還沒有任何保險箱，此保險箱就會佔據該節點
- 否則若這個要放入的保險箱裡面的金塊比在該節點的保險箱還要多，他會被往右邊送
- 否則就往左邊送
- 必須送到他占用一個節點為止

以上圖為例

- 第一個放進來的保險箱有 8 個金塊
- 第二個有 10 個，因此他被放在右邊
- 第三個有 14 個，因此第一步會先往右送，發現右邊的節點也有保險箱了，因而再次被往右送
- 第四個有 3 個，於是被放在左邊
- 其他依此類推

由於分類器內部構造太大，不方便進入，所以開發者在分類器中內建一套電梯探訪順序，以及記錄規則供使用者參考，避免保險箱被重複計算或是漏算。如下

- 當此節點的左邊有保險箱，電梯優先向左
- 當此節點的左邊的保險箱都被記錄過了，或是左邊根本沒有保險箱，紀錄當前所在的節點裡面保險箱的金條數量
- 然後電梯向右

同樣以上圖為例

- 節點 8 的左邊有其他保險箱 >> 電梯向左
- 進到節點 3 >> 同上 >> 電梯向左
- 進到節點 1 >> 左右邊都沒有保險箱 >> 記下 1 >> 電梯回到節點 3
- 左邊都記錄過了 >> 記下 3 >> 右邊有保險箱 >> 電梯向右
- 進到節點 6 >> 左邊有其他保險箱 >> 電梯向左
- 進到節點 4 >> 左右邊都沒有保險箱 >> 記下 4 >> 電梯回到節點 6
- 左邊都記錄過了 >> 記下 6 >> 右邊有保險箱 >> 電梯向右
- 進到節點 7 >> 左右邊都沒有保險箱 >> 記下 7 >> 電梯回到節點 6
- 電梯回到節點 3 >> 電梯回到節點 8 >> 左邊保險箱紀錄完畢 >> 記下 8 >> 右邊有保險箱 >> 電梯向右
- 進到節點 10 >> 左邊沒有保險箱 >> 記下 10 >> 右邊有保險箱 >> 電梯向右
- 進到節點 14 >> 左邊有保險箱 >> 電梯向左
- 進到節點 13 >> 左右邊都沒有保險箱 >> 記下 13 >> 電梯回到節點 14
- 左邊保險箱紀錄完畢 >> 記下 14
- 電梯回到節點 10 >> 電梯回到節點 8
- 紀錄完畢

最後結果如下

1 3 4 6 7 8 10 13 14

## 輸入說明 :

- 第一行輸入 $1$ 個數字 $t$ ，代表有 $t$ 比測試資料
- 每筆測資第一行輸入 $1$ 個數字 $n$ ，表示一開始的保險箱有幾個
- 第二行輸入 $n$ 個數字 $a_1,a_2...a_n$ ， $a_i$ 代表第 $i$ 個放入分類器的保險箱有幾塊金條

$t \leq 10$
$n$ $,$ $a_i$ $\leq 10^5$

## 輸出說明 :

僅全部的保險箱放完以後進行一次紀錄

## 範例輸入1 :

2
3
3 2 1
9
8 10 14 3 1 6 7 4 13

## 範例輸出1 :

1 2 3
1 3 4 6 7 8 10 13 14

## 子題組與配分

- 第一子題組 : 放入的順序為由大到小，占 10%
- 第二子題組 : 無其他限制，占 90%

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }

    sort(v.begin(),v.end());

    for(auto i:v){
        cout<<i<<" ";
    }
    cout<<"\n";
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}