제출 #1312972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312972		zbyszko	중앙값 배열 (balkan11_medians)	C++20	10 / 100	98 ms	13356 KiB

medians

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

using ull = unsigned long long;
using ll = long long;
using pii = pair<ll,ll>;
#define x first
#define y second

set<int> used;

void zm(int& a,int& b){
    while(used.find(a)!=used.end()) a++;
    while(used.find(b)!=used.end()) b--;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin >> n;
    vector<int> m(n);
    vector<int> inx(n);
    vector<pii> ans(n);
    int mini=INT32_MAX;
    for(int i=0;i<n;i++){
        cin >> m[i];
        inx[i]=i;
        used.insert(m[i]);
    }
    sort(inx.begin(),inx.end(),[&m](int a,int b){
        return m[a]>m[b];
    });
    int l=1,r=2*n-1;
    while(used.find(l)!=used.end()) l++;
    while(used.find(r)!=used.end()) r--;
    int cur=-1;
    for(int i:inx){
        if(i==0){
            ans[0].x=m[0];
            cur=m[0];
            continue;
        }
        if(m[i]==cur){
            if(m[i]==m[i-1]){
                ans[i].x=l;
                ans[i].y=r;
                used.insert(l);
                used.insert(r);
                zm(l,r);
            }
            else if(m[i]>m[i-1]){
                ans[i].x=r;
                used.insert(r);
                zm(l,r);
                ans[i].y=r;
                used.insert(r);
                zm(l,r);
            }
            else{
                ans[i].x=l;
                used.insert(l);
                zm(l,r);
                ans[i].y=l;
                used.insert(l);
                zm(l,r);
            }
        }
        else if(m[i]>m[i-1]){
            ans[i].x=m[i];
            ans[i].y=r;
            used.insert(r);
            zm(l,r);
        }
        else{
            ans[i].x=m[i];
            ans[i].y=l;
            used.insert(l);
            zm(l,r);
        }
        cur=m[i];
        
    }
    cout << ans[0].x << " ";
    for(int i=1;i<n;i++){
        cout << ans[i].x << " " << ans[i].y << " ";
    }
    return 0;
}

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