/* 8 6 5 3 1 10 ->分解(a[i], a[i+k], a[i+2k], …と選んでグループiを作る)-> 8 5 1 6 3 10 同じ行の数字同士で交換になる。 -> 各グループで交換回数を独立に最小化すればよい。 グループ内では操作が隣り合った2要素を交換になる。 -> 反転数を考えると、バブルソートが最善!! バブルソートして昇順にならなければ、-1を出力すればよい。 O(N^2/K) … 計算量が最高に面白いです! */ #include #include #include using namespace std; int n, k; int a[1000]; int bubbleSort(vector &a) { int i, j, cnt = 0; for (i = 0; i < a.size() - 1; i++) { for (j = a.size() - 1; j > i; j--) { if (a[j-1] > a[j]) { cnt++; swap(a[j-1], a[j]); } } } return cnt; } int main() { int i, j; cin >> n >> k; for (i = 0; i < n; i++) cin >> a[i]; vector arrays[1000]; for (i = 0; i < n; i++) arrays[i % k].push_back(a[i]); int ans = 0; for (i = 0; i < k; i++) if (arrays[i].size() >= 2) ans += bubbleSort(arrays[i]); for (i = 0; i < n; i++) a[i] = arrays[i % k][i / k]; for (i = 0; i < n - 1; i++) if (a[i] > a[i+1]) break; if (i < n - 1) ans = -1; cout << ans << endl; return 0; }