2025. 01. 14

제목에 플랜디가 없는 이유는.. 안했기 때문이죠

 

대신 재밌는 다이아를 풀었어요

 

[BOJ 20345] XOR Sort

배열 $A$의 인접한 두 원소에 대해 $A_i = A_i \oplus A_{i+1}$ 혹은 $A_{i+1} = A_i \oplus A_{i+1}$로 바꾸는 연산을 최대 $40\,000$회 할 수 있다.

1. 배열 $A$의 원소가 모두 다르고 배열의 크기가 $200$ 이하일 때, 배열 $A$를 오름차순으로 정렬하시오.
2. 배열 $A$의 크기가 $1\,000$ 이하일 때, 배열 $A$를 비내림차순으로 정렬하시오.

이때 결과 배열의 원소들은 초기 배열의 원소들과 같든 다르든 상관은 없습니다.

우선, $2$번 문제를 먼저 풀었습니다. 배열의 모든 원소들에 대해서 켜져 있는 최상단 비트의 최댓값이 있다고 하면, 그 비트를 배열 전체에서 모두 없애는건 불가능하다는 걸 알 수 있습니다.

그렇다면 최상단비트는 무조건 가장 오른쪽으로 옮겨줘야겠죠. 만일 $i$번 위치에 비트가 켜져있고 $i+1$번 위치에 꺼져있다면, 연산 $(i+1, i)$, $(i, i+1)$을 진행하면 비트가 옮겨갑니다. (둘 다 켜져 있다면 $(i, i+1)$만 해서 $i$번 위치의 최상단 비트를 끌 수 있습니다)

이렇게 해서 켜져있는 비트들 중 최상단 비트가 $N$번째 원소에만 켜져 있도록 만들겁니다. 최악의 횟수는 대충 $2N$일겁니다. 이제 해당 원소를 무시하고 $1$번 원소부터 $N-1$번 원소에 대해 같은 문제를 풀 수 있습니다.

이를 반복하면 약 $2 \times 20 \times 1000$번의 연산으로 문제를 해결할 수 있습니다. ($20$은 비트 개수)

 

이제 $1$번 문제를 풉시다.

여기서는 모든 원소가 다르기 때문에, 각 원소의 값을 유지하면서 정렬하고 싶다는 생각을 할 수 있습니다.

우선, 다음과 같은 관찰을 할 수 있습니다. $i$, $i+1$번 원소에 대해 연산 $(i+1, i)$, $(i, i+1)$, $(i+1, i)$를 진행할겁니다. 그럼 다음과 같이 됩니다.

$$(A_{i}, A_{i+1}) \to (A_{i}, A_{i} \oplus A_{i+1}) \to (A_{i+1}, A_{i} \oplus A_{i+1}) \to (A_{i+1}, A_{i})$$

이걸 토대로 버블정렬을 하면, $40\,000$보다 좀 더 걸린다는 것을 알 수 있습니다. 따라서 좀 더 효율적으로 해줘야 하는데, 저는 다음과 같이 구성했습니다. 일단 대충 $N=6$이라고 가정하면 초기 배열은 이렇습니다.

$$(A_1, A_2, A_3, A_4, A_5, A_6)$$

여기서 $(1, 2), (2, 3), \dots, (N-1, N)$ 연산을 해줍니다.

$$(A_1 \oplus A_2, A_2 \oplus A_3, A_3 \oplus A_4, A_4 \oplus A_5, A_5 \oplus A_6, A_6)$$

만약 초기 배열에서 $A_5$가 가장 큰 원소였다고 하면, $A_5$를 가장 오른쪽으로 밀어야 합니다. 따라서 $(6, 5)$ 연산을 해주면 다음처럼 됩니다.

$$(A_1 \oplus A_2, A_2 \oplus A_3, A_3 \oplus A_4, A_4 \oplus A_5, A_5 \oplus A_6, A_5)$$

이후, $1$번부터 $5$번까지의 모든 원소에서 $A_5$를 제거합니다. 이는 $(4, 5)$, $(5, 6)$을 하면 되겠죠.

$$(A_1 \oplus A_2, A_2 \oplus A_3, A_3 \oplus A_4, A_4 \oplus A_6, A_6, A_5)$$

이제 이걸 쭉 반복하면 정렬이 됩니다.

계산해보면 최악일 때 연산 횟수를 $39\,999$번 쓰는 것 같습니다. 

저는 우선순위 큐를 사용해서 현재 가장 큰 수를 찾고, pb_ds를 사용해서 자신 앞의 원소들 중 이미 정렬해서 오른쪽으로 빠진 원소의 개수를 세줬습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>

int n, s;
int a[1003];
vector<pair<int, int>> r;

void f1(){
    priority_queue<pair<int, int>> pq;
    ordered_set os;
    for(int i=1; i<=n; i++){
        pq.push({a[i], i});
        os.insert(i);
    }
    for(int i=1; i<n; i++){
        r.push_back({i, i+1});
    }
    int mx = n;
    while(!pq.empty()){
        auto [x, p] = pq.top(); pq.pop();
        auto idx = os.order_of_key(p)+1;
        for(int i=idx+1; i<=mx; i++){
            if(i == 1) continue;
            r.push_back({i, i-1});
        }
        for(int i=idx; i<=mx; i++){
            if(i == 1) continue;
            r.push_back({i-1, i});
        }
        mx--;
        os.erase(p);
    }
}

void f2(){
    int mx = n-1;
    for(int i=19; i>=0; i--){
        int cur = 1<<i;
        int chk = 0;
        for(int j=1; j<=mx; j++){
            if(a[j]&cur){
                chk = 1;
                if(a[j+1]&cur){
                    r.push_back({j, j+1});
                    a[j] ^= a[j+1];
                }
                else{
                    r.push_back({j+1, j});
                    a[j+1] ^= a[j];
                    r.push_back({j, j+1});
                    a[j] ^= a[j+1];
                }
            }
        }
        if(chk) mx--;
    }
}

int main(){
    scanf("%d %d", &n, &s);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    if(s == 1){
        f1();
    }
    else{
        f2();
    }
    printf("%d\n", r.size());
    for(auto [x, y] : r){
        printf("%d %d\n", x, y);
    }
}