제출 #1153486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153486		Ciprian	중앙값 배열 (balkan11_medians)	C++20	0 / 100	62 ms	11848 KiB

medians

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

set<int> mis;
vector<int>A;
void Mex(int n){
    for (int i = 1; i <=2*n-1; i++)
        mis.insert(i);

    for (int x : A) {
        
        if(mis.find(x)!=mis.end())mis.erase(x);
    }
}

int mex() {
    return *mis.begin();
}

void update(int new_value) {
    
    if(mis.find(new_value)!=mis.end())mis.erase(new_value);
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("medians.in", "r", stdin);
    //freopen("medians.out", "w", stdout);
    
    int n;
    cin>>n;
    vector<int> a(n+2);
    vector<bool>check(2*n+1);
    for(int i=1; i<=n; i++)cin>>a[i];
    A.push_back(a[1]);
    check[a[1]]=true;
    Mex(n);
    
    int mx=2*n-1;
    

    for(int i=2; i<=n; i++){
        if(!check[a[i]]){
            check[a[i]]=true;
            check[mx]=true;
            A.push_back(a[i]);
            A.push_back(mx);
            
            update(a[i]);
            update(mx);
            mx--;
        }else{
            int m=mex();
            check[m]=true;
            check[mx]=true;
            A.push_back(m);
            A.push_back(mx);
            update(m);
            update(mx);
            
            mx--;
        }
    }for(auto e: A){
        cout<<e<<" ";
        
    }cout<<endl;

    return 0;
}

• Subtask 1: 0 / 65
• Subtask 2: 0 / 35