백준 2517 달리기 문제 풀이

백준저지 2517 달리기 문제 풀이입니다.

https://www.acmicpc.net/problem/2517

Counting Inversions 문제와 유사한 문제입니다.

풀이는 백준 10090번 문제 Counting Inversions를 참조하면 좋습니다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
pii A[500005];
pii T[500005];
int ans[500005];

void merge(int s, int m, int e) {
    int p1 = s;
    int p2 = m;
    int k = s;
    while (p1 < m && p2 < e) {
        if (A[p1].first <= A[p2].first) {
            T[k++] = A[p1++];
        } else {
            int advance = p1 - s;
            int origin_rank = A[p2].second;
            if (advance) {
                ans[origin_rank] -= advance;
                /*
                printf("%d의 원래 순위는 %d이고, %d개를 앞지를 수 있다.\n", A[p2].first, origin_rank, advance);
                for (int i=s; i < p1; i++) {
                    printf("\t%d를 앞지른다.\n", A[i]);
                } 
                */
            }
            T[k++] = A[p2++];
        }
    }
    
    while (p1 < m) {
        T[k++] = A[p1++];
    }
    
    while (p2 < e) {
        int advance = p1 - s;
        int origin_rank = A[p2].second;
        if (advance) {
            ans[origin_rank] -= advance;
            /*
            printf("%d의 원래 순위는 %d이고, %d개를 앞지를 수 있다.\n", A[p2].first, origin_rank, advance);
            for (int i=s; i < p1; i++) {
                printf("\t%d를 앞지른다.\n", A[i]);
            } 
            */
        }
        T[k++] = A[p2++];
    }
    
    for (int i=s; i < e; i++) {
        A[i] = T[i];
    }
    
}

void merge_sort(int s, int e)  {
    int m = (s + e) / 2;
    if (s < m) {
        merge_sort(s, m);
        merge_sort(m, e);
        merge(s, m, e);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    
    for (int i=1; i <= n; i++) {
        scanf("%d", &A[i].first);
        A[i].second = i;
        ans[i] = i;
    }
    
    merge_sort(1, n+1);
    
    for (int i=1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }
	return 0;
}