[18870]座標圧縮

[18870]座標圧縮

質問する

垂直線上のN個の座標X 1,X 2,...,XNがあります.この座標に座標圧縮を適用します.
Xiを座標圧縮した後、X'iの値はXi>Xjを満たす異なる座標の個数に等しくなければならない.
X1, X2, ..., XNに座標圧縮を適用すると、X"1,X"2,...,X'Nを印刷します.

入力

1行目はNです.
2行目は、スペースで区切られたX 1、X 2、…、XNをあげます.

しゅつりょく

1行目X「1,X」2,...,X'Nをスペース出力に分割します.

制限

1 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109

コード#コード#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    /* 빠른 cin cout */
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    /* 입력 */
    int N;
    cin >> N;
    vector<int> input, position;

    /* 풀이 */
    int tmp;
    for(int i = 0; i < N; i++) {
        cin >> tmp;
        input.push_back(tmp);
        position.push_back(tmp);
    }

    sort(position.begin(), position.end());
    position.erase(unique(position.begin(), position.end()), position.end());

    /* 출력 */
    for(int i = 0; i < N; i++) {
        cout << lower_bound(position.begin(), position.end(), input[i]) - position.begin() << ' ';
    }
}

追加の説明

positionというベクトルを並べ替えて重複を解消する2つのベクトルが作成されました.
各入力に対して下限を使用します.位置に見つかったインデックスは0から始まる順序と同じなので、インデックスの出力が必要です.

例

ソース:https://www.acmicpc.net/problem/18870