uva 716 - Commedia dell' arte(置換)

uva 716 - Commedia dell' arte(置換)

題目鏈接：uva 716 - Commedia dell' arte

題目大意：給定一個三維的八數碼，0表示空的位置，問說是否可以排回有序序列。

解題思路：對於n為奇數的情況，考慮三維八數碼對應以為狀態下去除0的時候逆序對數，偶數的情況下，考慮將0的位置轉移到（n，n，n）位置後對應序列的逆序對數。如果逆序對數為偶數即為可以，奇數不可以。

#include 
#include 
#include 

using namespace std;
typedef long long ll;
const int maxn = 1e6+5;

int n, arr[maxn], t[maxn];
int x, y, z;

ll merge_sort (int l, int r, int* a, int* b) {
    if (l == r)
        return 0;

    ll ret = 0;

    int mid = (r + l) / 2;
    int p = l, q = mid+1, mv = l;

    ret = merge_sort(l, mid, a, b) + merge_sort(mid + 1, r, a, b);

    while (p <= mid || q <= r) {
        if (q > r || (p <= mid && a[p] < a[q]))
            b[mv++] = a[p++];
        else {
            ret += mid - p + 1;
            b[mv++] = a[q++];
        }
    }

    for (int i = l; i <= r; i++)
        a[i] = b[i];
    return ret;
}

bool judge () {
    if (n&1) {
        ll ret = merge_sort(0, n*n*n-1, arr, t) - (z * n * n + x * n + y - 1);
        return (ret&1) == 0;
    }

    while (z != n - 1) {
        int p = z * n * n + x * n + y;
        z++;
        int q = z * n * n + x * n + y;
        swap(arr[p], arr[q]);
    }

    while (x != n - 1) {
        int p = z * n * n + x * n + y;
        x++;
        int q = z * n * n + x * n + y;
        swap(arr[p], arr[q]);
    }

    while (y != n - 1) {
        int p = z * n * n + x * n + y;
        y++;
        int q = z * n * n + x * n + y;
        swap(arr[p], arr[q]);
    }
    ll ret = merge_sort(0, n*n*n-2, arr, t);
    return (ret&1) == 0;
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {

        scanf("%d", &n);
        for (int k = 0; k < n; k++) {
            int Z = k * n * n;
            for (int i = 0; i < n; i++) {
                int X = i * n;
                for (int j = 0; j < n; j++) {
                    int tmp = Z + X + j;
                    scanf("%d", &arr[tmp]);
                    if (arr[tmp] == 0) {
                        x = i; y = j; z = k;
                    }
                }
            }
        }

        printf("%s\n", judge() ? "Puzzle can be solved." : "Puzzle is unsolvable.");
    }
    return 0;
}