시도 횟수: 1회

해결한 시간: 00:13

문제 번역(GPT)

핵심 아이디어

<aside> 💡

가장 이상적인 순열은 $n, n-1, n-2,...,2, 1$이다. 이를 $p'$이라고 하자.

$p_i = p'_i$인 가장 작은 $i$와 뒤에 가장 큰 값이 나오는 곳 사이를 뒤집으면 된다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n;
int a[200'001];

void solve()
{
    bool flag = true;
    
    cin >> n;

    int cur = n;
    int sidx = 0;
    int idx = -1;
    for(int i = 0; i<n; i++){
        cin >> a[i];
        if(flag){
            if(a[i] == cur){
                if(i == n-cur){
                    cur--;
                    sidx++;
                }
                else{
                    idx = i;
                    flag = false;
                }
            }
        }
    }
    if(idx == -1){
        for(int i = 0; i<n; i++) cout << a[i] <<" ";
        cout << "\\n";
        return;
    }

    for(int i = 0; i<sidx; i++){
        cout << a[i] <<" ";
    }
    for(int i = idx; i>=sidx; i--){
        cout << a[i] <<" ";
    }
    for(int i = idx+1; i<n; i++){
        cout << a[i] <<" ";
    }
    cout <<"\\n";
    // cout << idx<<"\\n";
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while (_tc--) solve();
    return 0;
}

복기