R623(Div.2) C. Restoring Permutation

 

bi = (ai*2-1,ai*2)일 때 1~2n 까지 숫자를 두는게 가능한지 보는 문제다

그리디로 내가 앞에서부터 작은수를 채워나가면 된다

 

이럴때는 upper_bound를 쓰자!!

 

먼저 set에 1~2n까지 나오지 않은 숫자를 담아준다

그리고 upper_bound를 통해 현재 위치를 만족시켜주는 가장 작은 숫자를 찾자

만약 없다면 -1!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool check[222];
int main(){
    int t; scanf(" %d",&t);
    while(t--){
        memset(check,0,sizeof(check));
        int n; scanf(" %d",&n);
        vector<int> barr(n),ans(n);
 
        for(int i=0;i<n;i++){
            scanf(" %d",&barr[i]);
            check[barr[i]]=true;
        }
        set<int> s;
        for(int i=1;i<=n*2;i++){
            if(check[i]) continue;
            s.insert(i);
        }
 
        bool c=true;
        for(int i=0;i<n;i++){
            auto pos = s.upper_bound(barr[i]);
            if(pos==s.end()){
                c=false; break;
            }
            ans[i]=*pos;
            s.erase(*pos);
        }
        if(!c){
            puts("-1"); continue;
        }
        for(int i=0;i<n;i++) printf("%d %d ",barr[i],ans[i]); puts("");
    }
}