ARC_110_C - Exoswap

[zeikar]

Problem link

https://atcoder.jp/contests/arc110/tasks/arc110_c

Problem Summary

배열이 주어지고, 임의의 순열 P의 순서대로 swap을 했을 때 오름차순이 되는지 확인하는 문제.

Solution

그리디하게 접근해보자.
가장 큰 수는 가장 오른쪽으로 이동해야 되므로 가장 큰 수부터 탐색을 진행한다.
오른쪽으로 swap이 가능하면 swap을 해주고 자기 위치까지 계속 swap을 한다. 일종의 버블 정렬 느낌.

이때 P가 순열이므로 visited를 넣어 한번 나온 수는 더 나오지 않게 처리한다.

Source Code

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int a[200001];
pair<int, int> map[200001];
bool visited[200001];

int main() {
	int n;
	cin >> n;


	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		map[i].first = a[i];
		map[i].second = i;
	}

	sort(map, map + n);

	vector<int> ans;

	for (int i = n - 1; i > 0; i--)
	{
		int val = map[i].first;
		int pos = map[i].second;

		// move
		if (pos < val - 1 && !visited[pos])
		{
			// swap
			int target = a[pos + 1];

			map[i].second = map[i - (val - target)].second;
			map[i - (val - target)].second = pos;

			a[pos] = target;
			a[pos + 1] = val;

			ans.push_back(pos);
			visited[pos] = true;
			i++;
		}
		else if (pos == val - 1)
		{
			continue;
		}
		else
		{
			ans.clear();
			break;
		}
	}

	if (ans.size() != n - 1)
	{
		cout << -1 << endl;
	}
	else
	{
		for (int i = 0; i < ans.size(); i++)
		{
			cout << ans[i] + 1 << endl;
		}
	}
}