#14684 줄서기

올림피아드 문제는 난이도보다 1.5배정도 더 어려운거 같다.
골드 3문제인데 쉽지 않았다. 그래도 올림피아드 문제들이 질이 너무 좋은듯.

 

핵심적인 관찰은 원래상태에서 어떻게 변화하는지를 관찰하는 것이다.

여기서 원래 상태라고 함은, 기본적으로 정렬되어 있는 상태 즉, $1,2,3.....n$ 에서 어떻게 변화하는지를 관찰하는 것이다. 해보자!

$swap(i,i+1)$은 이 문제에서 매우 매우 중요하다.
즉 인접한 원소를 swap하는 연산이 중요 접근법이다.
인접한 원소를 정렬하게 되면, (i,i+1)순서쌍이 추가되고, 끝이다. 중요한 점은 swap한번에, 순서쌍이 1개씩 추가된다는 점이다!


여기서 조금 발상적으로 중간 과정을 생략하면

주어진 순서쌍들이 (a,b)로 주어지고 a로 들어올때마다 A[a]++를 해주면,

옳은 연산이라면, A에 따라 정답은 유일하게 결정된다. (아마)
만약 주어진 정보가 올바르다면 i번째 원소는 i-1번째까지 구해진 상태에서, i+A[i]번째 원소에서 swap하면서 구해온 것이라는 결론이다.

말이 이상한데 ㅋㅋ

주어진 예제에서 $A[1]=2,A[3]=2,A[4]=1$이다.

$1 2 3 4 5$
A[1]=2니까 2번
$1 3 2 4 5$

$3 1 2 4 5$

A[2]=0이니까 넘어가고
A[3]=2니까 
$3 1 2 5 4$
$3 1 5 2 4$

A[4]=1이니까

 

$3 1 5 4 2$이다.
정답이 나왔다 굳.

-1인지 체크하는건 대충 다시 m번 해보면 된다.
전체 시간복잡도는 O(N+M)으로 해결가능하다.
근데 채점이 조금 느린거 보니 데이터가 많은듯!