algorithms/test.cpp at main · CroxxN/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 2e5 + 5;

int n, k;
int p[N];

bool check() {
    for (int i = 0; i < n; i++) {
        if (p[i] != i + 1) {
            int j = min(n-1, i+k);
            for (; j > i; j--) {
                if (p[j] == i+1) {
                    break;
                }
            }
            if ((i-1)/k != (j-1)/k) {
                return false;
            }
            while (i < j) {
                swap(p[i], p[j]);
                i += k;
                j -= k;
            }
        }
    }
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }

        bool sorted = check();
        if (sorted) {
            cout << 0 << endl;
            continue;
        }

        // Try one single swap
        for (int i = 0; i < n; i++) {
            if (p[i] == i+1) continue;

            int num_pos = (p[i] - 1) / k;
            int target_pos = num_pos * k;
            if (abs(i - target_pos) % k == 0 && abs(i - target_pos) != k) {
                swap(p[i], p[target_pos]);
                if (check()) {
                    cout << 1 << endl;
                } else {
                    cout << -1 << endl;
                }
                break;
            } else {
                cout << -1 << endl;
                break;
            }
        }
    }
    return 0;
}