Many Medians [AtCoder Regular Contest 095 C]

https://beta.atcoder.jp/contests/arc095/tasks/arc095_a

解法

https://beta.atcoder.jp/contests/arc095/submissions/2361369

よくよく考えると中央値となりうる候補は2種類しか無い。
配列Xをソートしたものを配列Aとすると、A[N/2-1]かA[N/2]のどちらかが答えになる。
A[N/2-1]が答えになる場合は消した数がA[N/2]～A[N-1]にある場合であり、
A[N/2]が答えになる場合は消した数がA[0]～A[N/2 - 1]にある場合である。
ある数を消す時はソート済みの数の中で最も早く出てくる所が消える。
よって、「idx[x] = ソート済み配列Aの中で数xが最も早く出てくる座標」を使って判別していこう。

int N, X[201010], A[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> X[i];
    rep(i, 0, N) A[i] = X[i];
    sort(A, A + N);
 
    map<int, int> idx;
    rrep(i, N - 1, 0) idx[A[i]] = i;
 
    rep(i, 0, N) {
        int j = idx[X[i]];
        if (j < N / 2) printf("%d\n", A[N / 2]);
        else printf("%d\n", A[N / 2 - 1]);
    }
}