This repository was archived by the owner on Sep 29, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path1285.cpp
More file actions
59 lines (56 loc) · 1.31 KB
/
1285.cpp
File metadata and controls
59 lines (56 loc) · 1.31 KB
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
#include <iostream>
using std::cin, std::cout, std::endl;
struct Context {
int *array;
int gasRemaining;
bool isSorted (int l, int r) {
for (int i = l + 1; i < r; ++i) {
if (array[i - 1] > array[i]) return false;
}
return true;
}
void mergeShuffle (int l, int r) {
if (!gasRemaining) return;
if (r - l < 2) return;
gasRemaining -= 2;
int mid = (l + r) / 2;
mergeShuffle(l, mid);
mergeShuffle(mid, r);
if (isSorted(l, r)) std::swap(array[mid - 1], array[mid]);
}
void mergeSort (int l, int r) {
++gasRemaining;
if (isSorted(l, r)) return;
int mid = (l + r) / 2;
mergeSort(l, mid);
mergeSort(mid, r);
}
};
int main () {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
int length, count;
cin >> length >> count;
if (count % 2 == 0 || count < 0) {
cout << "-1\n";
return 0;
}
int array[length];
for (int i = 0; i < length; ++i) array[i] = i + 1;
Context ctx {
.array = array,
.gasRemaining = count - 1,
};
ctx.mergeShuffle(0, length);
if (ctx.gasRemaining) {
cout << "-1\n";
return 0;
}
#ifdef DEBUG
ctx.mergeSort(0, length);
cout << ctx.gasRemaining << ' ' << count << endl;
#endif
for (int i = 0; i < length - 1; ++i) cout << array[i] << ' ';
cout << array[length - 1] << endl;
return 0;
}