[c++] 백준 #5000 빵정렬

< 풀이 >

정렬을 할 때마다 규칙성을 찾아야 하는 게 문제인데 나는 그걸 못 찾아서 친구의 풀이를 듣고 깨달음을 얻었다.

정렬을 할 때마다 역순 pair의 홀짝성이 유지가 된다는 것이 특징.

예를 들어 (4, 3, 2)는 (4, 3), (3, 2), (4, 2) 총 3개의 역순 pair를 가진다.

이를 빵정렬하면 (2, 4, 3)이 되는데 이거는 역순 pair를 (4, 3) 하나만 가진다.

 

그러면 역순 pair의 수가 홀수인 순열은 아무리 빵정렬을 해도 역순 pair의 수가 홀수개이다. 역순 pair 수가 짝수개가 죽어도 될 수 없다는 의미.

그러므로 주어진 두 input의 역순 pair 수를 세보고 둘다 짝수거나 둘다 홀수면 Possible, 아니면 Impossible을 띄우면 된다.

 

역순 pair를 세는 방법은 펜윅트리를 통해 쉽게 할 수 있다.

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define N_MAX 100010

int tree[N_MAX];
int N; 
// 내림차순 정렬
bool comp(ii a, ii b){
    if (a.first == b.first){
        return a.second > b.second;
    }
    else return a.first > b.first;
}

void insert(int i, int d) {
	while (i <= N) {
		tree[i] += d;
		i += (i & -i);
	}
}
 
int get(int i) {
	int ret = 0;
	while (i) {
        ret += tree[i];
		i &= (i - 1);
	}
	return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    vector<ii> ori(N+1, {0, 0});
    vector<ii> snd(N+1, {0, 0});
    for(int i=1; i<=N; i++) {
        cin >> ori[i].first;
        ori[i].second = i;
    }
    for(int i=1; i<=N; i++) {
        cin >> snd[i].first;
        snd[i].second = i;
    }

    sort(ori.begin()+1, ori.end(), comp);
    sort(snd.begin()+1, snd.end(), comp);

    // 거꾸로 된 pair 수를 펜윅으로 계산한다.
    int n_rev_pair = 0;
    for(int i=1; i<=N; i++){
        n_rev_pair += get(ori[i].second); // 제일 큰 애의 인덱스에서 값을 읽음
        insert(ori[i].second, 1);
    }
    memset(tree, 0, sizeof(tree));
    int n_rev_pair2 = 0;
    for(int i=1; i<=N; i++){
        n_rev_pair2 += get(snd[i].second); // 제일 큰 애의 인덱스에서 값을 읽음
        insert(snd[i].second, 1);
    }
    if ((n_rev_pair % 2) == (n_rev_pair2 % 2)){
        cout << "Possible\n";
    }
    else cout << "Impossible\n";

    return 0;
}