-
Notifications
You must be signed in to change notification settings - Fork 2
/
absolute-permutation.js
113 lines (106 loc) · 2.79 KB
/
absolute-permutation.js
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;
process.stdin.on('data', function (data) {
input_stdin += data;
});
process.stdin.on('end', function () {
input_stdin_array = input_stdin.split("\n");
main();
});
function readLine() {
return input_stdin_array[input_currentline++];
}
/////////////// ignore above this line ////////////////////
function absolute(n, k) {
if (k > n / 2) return [-1]
if (k == 0) return new Array(n).fill(0).map((x, index) => index + 1)
let p = new Array(n).fill(0);
let pos = new Array(n + 1).fill(-1);
for (let i = 0; i < k; i++) {
const ii = i + 1;
p[i] = ii + k;
pos[ii + k] = i;
let jj = ii + k + k;
while (jj + k <= n) {
const j = jj - 1;
p[j] = jj + k;
pos[jj + k] = j;
jj += k + k;
}
}
// console.table({p})
for (let i = n - k; i < n; i++) {
if (p[i]) continue;
const ii = i + 1;
if (pos[ii - k] != -1) return [-1]
p[i] = ii - k;
pos[ii - k] = i;
let jj = ii - k - k;
while (jj - k > 0) {
const j = jj - 1;
if (p[j]) continue;
p[j] = jj - k;
pos[jj - k] = j;
jj -= k + k;
}
}
let check = true;
while (check) {
check = false;
for (let i = k; i < n - k; i++) {
if (p[i] != 0) continue;
const ii = i + 1;
const ii1 = ii - k;
const ii2 = ii + k;
// console.table({ii, p, pos});
if (pos[ii1] != -1 && pos[ii2] != -1) return [-1];
if (pos[ii1] == -1 && pos[ii2] == -1) continue;
if (pos[ii1] == -1) {
p[i] = ii1;
pos[ii1] = i;
if (!check) check = true;
continue;
}
if (pos[ii2] == -1) {
p[i] = ii2;
pos[ii2] = i;
if (!check) check = true;
}
}
}
check = true;
while (check) {
check = false;
for (let i = k; i < n - k; i++) {
if (p[i] != 0) continue;
const ii = i + 1;
const ii1 = ii - k;
const ii2 = ii + k;
if (pos[ii1] != -1 && pos[ii2] != -1) return [-1];
if (pos[ii1] == -1) {
p[i] = ii1;
pos[ii1] = i;
if (!check) check = true;
continue;
}
if (pos[ii2] == -1) {
p[i] = ii2;
pos[ii2] = i;
if (!check) check = true;
}
}
}
return p;
}
function main() {
var t = parseInt(readLine());
for(var a0 = 0; a0 < t; a0++){
var n_temp = readLine().split(' ');
var n = parseInt(n_temp[0]);
var k = parseInt(n_temp[1]);
console.log(absolute(n, k).join(' '));
}
}