HackerRank Absolute Permutation(Algorithms>Implementation)

題目:
我們定義P是前N個自然數的其中一種排列，也就是[1, N]裡面的正整數的排列。
定義posi是i在這個排列裡面所在的位置。
如果abs(posi-i) = K對每個[1, N]裡面的i都成立的話，
我們叫這個排列為絕對排列(Absolute Permutation)
給定N和K，印出字典順序最小的絕對排列P；
若不存在絕對排列，印出-1。

輸入:
第一行為T，代表總測資項數。
每個接下來的T行都有2個以空格分開的整數，
為該次測項的N和K。

限制:
1<=T<=10
1<=N<=10的5次方
0<=K<N

輸出:
在新的一行印出對該測項字典順序排列最小的絕對排列，
沒有絕對排列的話就印出-1。

範例輸入:

3
2 1
3 0
3 2

範例輸出:

2 1
1 2 3
-1

解題:
請同步參閱code內的註解。
在主函式內首先將arr填滿，
留意當k為0時，直接印出陣列即為解。

當k不等於0呢?
我們先假設絕對排列存在，
那麼i就必須跟i+k換(這樣才會有k的絕對差)，
那麼這樣思考的話，我們就可以用2k為一個區間來計算。
0, 1, ..., k-1 -> k+0, k+1, ... k+k-1這樣子做對照，
然後下一組區間從0+2k開始。
那麼接下來就是每次跳2k來看每個j能不能跟j+k交換。
也就是
i=0 : 0, k -> 2k, 3k -> 4k, 5k ...(if still < n)
i=1 : 1, k+1-> ......
以此類推，當中間碰到某次無法交換，就代表不存在這樣的絕對排列，

由於k被固定的狀況，0必須要跟k換，1必須要跟k+1換，
(因為沒得往前換，只能往後換)
所以前2k個數(0~2k-1)的換法都被固定了，
其後的數也無法跟前面的交換，
從而，2k~4k-1的換法也被固定了，
以此類推，此絕對排列要嘛不存在，
不然存在的話就是唯一解，那麼唯一解當然是最小囉XD!

Code：

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

// swap: make element i, j of the array arr[] swap with each other.
void swap(int *arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
/* permute: calculate absolute permutation of k, if NOT possible then return -1.
/  case: k==0
        Array itself is the answer, no need to swap anything.
  case: other
        Suppose there's an absolute permutation of the array, then element i must swap with element i+k,
        then the difference will be -k, +k.
        Since then, a section will be 2*k. 
        Ex: 0, 1, ..., k-1 -> k+0, k+1, ... k+k-1, and next round should start from 0+2k.
        We could start from i=0, each time adding 2*k to find if there's a pair to swap,
        that is, from 0, k -> 2k, 3k -> 4k, 5k ...(if still < n)
        (Notice that if we find a single num that can't be paired, we have to return -1.)
        
        Then i=1, i=2, i=3 ... ...
        And we could get the array done with absolute permutation of k.
*/
int permute(int *arr, int k, int n){
    for(int i = 0; i < k; i++){
        for(int j = i; j < n; j += k*2){
            if(j + k >= n)                        
                return -1;
            else
                swap(arr, j, j+k);        
        }         
    }
    return 0;
}
int main(){
    int t; 
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        int n, k;
        scanf("%d %d",&n,&k);
        int arr[n];
        
        for(int i = 0; i < n; i++)
            arr[i] = i + 1;
        
        if(k == 0){
            for(int i = 0; i < n; i++)
                printf("%d ", arr[i]);
        }else{
            if(permute(arr, k, n) == -1)
                printf("-1");
            else
                for(int i = 0; i < n; i++)
                    printf("%d ", arr[i]);            
        }
        printf("\n");
    }
    return 0;
}