SPOJ GENERAL: sorting by swaps of distance k

I have been trying to solve this simple problem on SPOJ for quite some time now, but I keep on getting TLE (Time limit exceeded) for some reason.

Since the problem is in Portuguese, a brief description of the problem is like this (without the story):


You are given an array of size N, you have to arrange the array in
ascending order, such that an element can only be swapped with
elements which are at a distance k from it. If the array can be
sorted then print the number of swaps required to arrange them in
ascending order, if it cannot be sorted print impossivel.

This is my code:

#include 
#include 

using namespace std;
int a[100005];
int main() {
    int t;
    int n, k;
    scanf("%d", &t); //number of test cases
    while(t--) {
        scanf("%d %d", &n, &k);
        bool result = true;
        int count = 0;

        for(int i = 0; i  0; i = i - k) {
            int j = 0;
            for( ; j  a[j + k]) {
                    int temp = a[j];
                    a[j] = a[j + k];
                    a[j + k] = temp;
                    count++;
                }
            }

            for( ; j  a[j + 1]) {
                    result = false;
                    break;
                }
            }

            if(!result)
                break;
        }
        if(result)
            printf("%d\n", count);
        else
            printf("impossivel\n");
    }
}

My logic : I perform N/k iterations on the array. I initialize the loop variable i to N. In each iteration I check i-k elements with the element at a distance k from it, if they are to be swapped then I swap them and increment the number of swaps needed, else I do nothing. Then I check the elements from i-k to i, if they are in ascending order, if not I break the loop and print "impossivel", else I change i to i-k and again perform the loop. By my logic after every iteration the last k elements will be in ascending order, if is possible to sort them, since at every step I

The above code can be optimized a little by below changes.

Replace this

for( ; j  a[j + k]) {
                int temp = a[j];
                a[j] = a[j + k];
                a[j + k] = temp;
                count++;
            }
        }

        for( ; j  a[j + 1]) {
                result = false;
                break;
            }
        }

        if(!result)
            break;

By

int  j = i-k;
        int x = 0;
        int tmp[i/k]; // Do check for i==0 here 
        for(int j = i; j >= 0; j -= k){
            tmp[x] = a[j];  
            x++;
        }
        sort(tmp);
        for(int j = i; j >= 0; j -= k){
             a[j] = tmp[x]; x--; 
        }

Add a check outside the main loop if its sorted or not.
But still this will be in order of \$O(N*KlogK)\$ which in worst cases \$O(N^2logN)\$. You might still get the TLE with that.

We can solve this in \$O(NlogN)\$. Trying thinking of solution in which you sort this a keeping original indexes of each element. Then calculate the number of swap by comparing the old index with new one.

StackExchange Code Review Q#133214, answer score: 3