시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 151 | 73 | 59 | 44.361% |
아이잔은 N개의 정수 S[0], S[1], ..., S[N-1]로 이루어진 수열 S를 가지고 있다. 수열은 0부터 N-1까지 서로 다른 N개의 정수로 이루어져있다. 아이잔은 두 수의 위치를 바꾸며 이 수열을 오름차순으로 정렬하려고 한다. 아이잔의 오랜 친구인 에르맥도 수열에서 두 수를 바꾸는데, 아이잔과는 다르게 정렬하려는 목적 없이 아무렇게나 바꾼다.
아이잔과 에르맥은 라운드를 거치며 수열을 조작한다. 각 라운드마다, 에르맥이 먼저 위치 바꾸기를 하고 그 다음 아이잔이 위치 바꾸기를 한다. 위치 바꾸기에 대해서 좀 더 자세히 말하자면, 바꿀 두 위치를 정하고 그 위치에 있는 값을 맞바꾼다. 이때 정하는 두 위치가 다를 필요는 없다. 만약 정한 두 위치가 같으면 수열에 아무런 변화가 없다.
아이잔은 에르맥이 수열 S를 정렬하려는 목적 없이 아무렇게나 바꾼다는 사실을 알고 있다. 더 나아가서 라운드를 시작하기 전부터 에르맥이 어떻게 위치 바꾸기를 할 건지 미리 다 알고 있다. 에르맥은 M 라운드에 대한 계획을 가지고 있다. 라운드의 번호를 순서대로 0 부터 M-1 까지 매겼을 때, i번 라운드에서 에르맥이 바꿀 두 위치는 X[i]와 Y[i]이다.
아이잔은 수열 S를 오름차순으로 정렬하길 원한다. 각 라운드를 시작하기 전에 만약 수열이 이미 정렬되어 있다면 라운드를 더 이상 진행하지 않고 멈출 수 있다. 처음 수열 S에 대한 정보와 에르맥이 M 라운드 동안 어떻게 위치 바꾸기를 할지에 대한 정보가 주어졌을 때, 아이잔이 어떻게 위치 바꾸기를 해야할지 구하시오. 언제나 M 라운드 안에 정렬이 가능하도록 입력이 주어진다.
만약 어떤 라운드에서 에르맥이 위치 바꾸기를 한 뒤 수열이 정렬되어 있다면, 아이잔은 같은 두 위치를 맞바꿔주면 된다 (예를 들어 0번 위치와 0번 위치). 그러면 이 라운드의 끝에서 수열 S는 정렬되고 아이잔은 멈출 수 있다. 또한 처음부터 수열 S가 정렬되어 있다면 필요한 라운드의 최소 수는 0 이다.
예제 1
이러한 상황에서 아이잔은 3 라운드 만에 수열 S를 0, 1, 2, 3, 4로 정렬할 수 있다. 아이잔은 (0, 4), (1, 3) 그리고 (3, 4) 순서대로 위치 바꾸기를 하면 된다.
아래 표는 각 위치 바꾸기마다 수열 S의 내용이 어떻게 바뀌는지 나타내고 있다.
라운드 | 사람 | 바꿀 두 위치 | 수열 |
---|---|---|---|
초기 | 4, 3, 2, 1, 0 | ||
0 | 에르맥 | (0, 1) | 3, 4, 2, 1, 0 |
0 | 아이잔 | (0, 4) | 0, 4, 2, 1, 3 |
1 | 에르맥 | (1, 2) | 0, 2, 4, 1, 3 |
1 | 아이잔 | (1, 3) | 0, 1, 4, 2, 3 |
2 | 에르맥 | (2, 3) | 0, 1, 2, 4, 3 |
2 | 아이잔 | (3, 4) | 0, 1, 2, 3, 4 |
예제 2
이러한 상황에서 아이잔은 3 라운드 만에 수열 S를 정렬할 수 있다. 아이잔은 (1, 4), (4, 2) 그리고 (2, 2) 순서대로 위치 바꾸기를 하면 된다.
아래 표는 각 위치 바꾸기마다 수열 S의 내용이 어떻게 바뀌는지 나타내고 있다.
라운드 | 사람 | 바꿀 두 위치 | 수열 |
---|---|---|---|
초기 | 3, 0, 4, 2, 1 | ||
0 | 에르맥 | (1, 1) | 3, 0, 4, 2, 1 |
0 | 아이잔 | (1, 4) | 3, 1, 4, 2, 0 |
1 | 에르맥 | (4, 0) | 0, 1, 4, 2, 3 |
1 | 아이잔 | (4, 2) | 0, 1, 3, 2, 4 |
2 | 에르맥 | (2, 3) | 0, 1, 2, 3, 4 |
2 | 아이잔 | (2, 2) | 0, 1, 2, 3, 4 |
수열 S와 정수 M, 그리고 X, Y가 주어진다.
아이잔이 수열 S를 정렬하기 위해 어떻게 위치를 바꿀지에 대해 계산하자.
다음 함수 findSwapPairs를 구현해야 한다.
M라운드 혹은 보다 더 일찍 정렬 가능하도록 입력이 주어진다.
findSwapPairs가 리턴한 값을 출력한다.
다음 양식에 따라 출력한다:
5 4 3 2 1 0 6 0 1 1 2 2 3 3 4 0 1 1 2
3 0 4 1 3 3 4
Olympiad > International Olympiad in Informatics > IOI 2015 > Day 2 5-1번