[CODEFORCES] Card Deck

Problem

You have a deck of n cards, and you'd like to reorder it to a new one.
Each card has a value between 1 and n equal to $p_i$. All $p_i$ are pairwise distinct. Cards in a deck are numbered from bottom to top, i. e. $p_i$ stands for the bottom card, $p_n$ is the top card.

In each step you pick some integer k > 0, take the top k cards from the original deck and place them, in the order they are now, on top of the new deck. You perform this operation until the original deck is empty. (Refer to the notes section for the better understanding.)

Let's define an order of a deck as $\sum_{i=1}^n n^{n-i}\cdot p_i$

Given the original deck, output the deck with maximum possible order you can make using the operation above.

 

Input

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

The first line of each test case contains the single integer $n (1≤n≤10^5)$ — the size of deck you have.

The second line contains n integers $p_1, p_2,…,p_n (1≤p_i≤n; p_i≠p_j\ if\ i≠j)$ — values of card in the deck from bottom to top.

It's guaranteed that the sum of n over all test cases doesn't exceed $10^5$.

 

Output

For each test case print the deck with maximum possible order. Print values of cards in the deck from bottom to top.

If there are multiple answers, print any of them.

 

Input	Output
4 4 1 2 3 4 5 1 5 2 4 3 6 4 2 5 3 6 1 1 1	4 3 2 1 5 2 4 3 1 6 1 5 3 4 2 1

 

CODE

#include <bits/stdc++.h>

using namespace std;

int card[100001];
int idx[100001];
bool used[100001];

void solve(int n)
{
    int cpyCard[100001];
    copy(card + 1, card + 1 + n, cpyCard + 1); // 처음에 입력받은 카드 저장
    sort(card + 1, card + n + 1, [&](int u, int v){ return u > v; }); // 내림차순 정렬
    
    for(int i = 1, end = n; i <= n; i++) // 정렬된 카드에 대한 반복문
    {
        if(!used[card[i]])
        {
            int nextEnd = idx[card[i]] - 1;
            for(int j = idx[card[i]]; j <= end; j++) // 처음에 입력받은 카드에 대한 반복문
            {
                cout << cpyCard[j] << ' ';
                used[cpyCard[j]] = true;
            }
            end = nextEnd;
        }
    }
    cout << '\n';
}

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

    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            cin >> card[i];
            idx[card[i]] = i;
        }
        solve(n);
        memset(card, 0, sizeof(card));
        memset(idx, 0 ,sizeof(idx));
        memset(used, false, sizeof(used)); // 배열 초기화
    }
}

 

COMMENT

 order of a deck 이라는 것을 $\sum_{i=1}^n n^{n-i}\cdot p_i$로 정의 해 놓았는데, 어짜피 $1\le p_i\le n$ 이기 때문에 가장 큰 숫자가 적힌 카드부터 차례로 뽑으면 된다. ($\sum_{i=0}^{n-1} 2^i = 2^n-1 \le 2^n$임을 생각 해보자.) 

 따라서 가장 처음 받은 카드의 위치를 저장해두고, 내림차순으로 정렬한 뒤에 앞에서부터 하나씩 카드 위치를 확인하면서 그 위치부터 맨 위 카드까지를 뽑으면 된다. 나는 카드의 사용여부를 저장하는 배열을 사용하여 구현했는데 디테일한 것은 각자 알아서 구현하면 된다. 이상 끝!(￣▽￣)"

 

도움이 되셨다면 공감 꾸욱! 부탁드립니다 ~~!!😊