[Atcoder] ABC306 :: C - Centers

간단한 정렬 문제이다.
N이 주어지고 3 * N개의 입력으로 숫자들이 입력된다. 이때 i (1 <= i <= N)에 속하는 숫자들은 반드시 3번 입력이 된다.

이때, 각 i가 2번째로 입력되는 인덱스를 기준으로, 정렬을 해서 출력을 하라고 한다. 
N이 1e5이하이므로, O(N) 짜리 배열을 하나 만들고, 각 숫자가 몇번 입력되었는지 count하자. 2번째로 입력된 순간 vector에 넣고 인덱스를 기준으로 정렬을 하면 된다.

#include<iostream>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#define X first
#define Y second
using namespace std;
int N, cnt[100010];
typedef pair<int, int> pii;
vector<pii> v;

bool compare(pii a, pii b) {
    return a.Y < b.Y;
}

int main() {
    cin >> N;
    for (int i=0; i<3*N; i++) {
        int x;
        cin >> x;
        cnt[x]++;
        if (cnt[x] == 2) {
            v.push_back({x, i});
        }
    }
    sort(v.begin(), v.end(), compare);
    for (auto curr : v) {
        cout << curr.X << ' ';
    }
}