OSgood의 개발일기

[백준] 2517 달리기 본문

Algorithm/Algorithm 문제 연습

[백준] 2517 달리기

OSgood 2020. 3. 29. 05:21

#include 
#include 

#define MAX_INT 1000000000

using namespace std;
using ll = long long;

struct node
{
int first, second, init;
};

node person[500002];
node temp[500002];
int N;
bool cmp(node a, node b)
{
return a.init < b.init;
}
void mergesort(int start, int end)
{
if (start == end)
{
return;
}
else if (end - start == 1)
{
if (person[end].first > person[start].first)
{
person[end].second--;
swap(person[start], person[end]);
}
}
else {
int left = start;
int mid = (start + end) / 2;
int right = mid + 1;
mergesort(left, mid);
mergesort(right, end);
for (int i = start; i <= end; i++)
{
if (left > mid)
{
temp[i] = person[right];
right++;
}
else if (right > end)
{
temp[i] = person[left];
left++;
}
else if (person[left].first < person[right].first)
{
temp[i] = person[right];
right++;
temp[i].second -= (mid - left + 1);
}
else
{
temp[i] = person[left];
left++;
}
}
for (int i = start; i <= end; i++) person[i] = temp[i];
}
}

int main()
{
ios::sync_with_stdio(false), cin.tie(NULL);

cin >> N;
for (int i = 0; i < N; i++)
{
cin >> person[i].first;
person[i].second = i;
person[i].init = i;
}
mergesort(0, N - 1);
sort(person, person + N, cmp);

for (int i = 0; i < N; i++)
cout << person[i].second + 1 << '\n';
}

'Algorithm > Algorithm 문제 연습' 카테고리의 다른 글

[백준] 2473 세 용액  (0) 2020.04.11
[백준] 2436 공약수  (0) 2020.03.29
[백준] 8986 전봇대  (0) 2020.03.22
[백준] 8984 막대기  (0) 2020.03.22
[백준] 8983번 사냥꾼  (0) 2020.03.21
Comments