[백준 30297번] Irreducible Permutation

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

 

순열P를 irreducible한 순열로 만드는 문제이다.

reducible의 정의로는 배열의 앞에서 하나씩 원소를 떼서 부분집합을 만들었을 때 순열을 만족하면 reducible한 순열이다.

(단, 자기 자신은 제외)

 

irreducible한 순열이 되기 위해서는...

i번째 원소까지의 최대값이 i보다 커질수 있도록 스왑하면서 이동하면 된다.

입력으로 주어지는 N의 값의 합이 500000이하인 것이 보장되므로 테스트 케이스 하나당 O(N)으로 해결하면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#define endl "\n"
using namespace std;

int t, n, m, tmp;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> t;
	while(t--){
		cin >> n;
		vector<int> arr(n,0);
		vector<int> ans;
		for(auto &i : arr) cin >> i;
		m = arr[0];
		for(int i = 0; i < n-1; i++){
			m = max(arr[i],m);
			if(i+1 >= m){
				m = arr[i+1];
				tmp = arr[i+1];
				arr[i+1] = arr[i];
				arr[i] = tmp;
				ans.push_back(i+1);
			}
		}
		if(ans.size()!=0){
			cout << ans.size() << endl;
			for(auto v:ans) cout << v << " ";
		}else{
			cout << 0 << endl;
		}
		cout << endl;
	}
}