QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#226861 | #3521. Insertion Order | gondozu | AC ✓ | 19ms | 15104kb | C++14 | 1.7kb | 2023-10-26 17:25:07 | 2023-10-26 17:25:08 |
Judging History
answer
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5+5, LOG = 20;
int left_child[N], right_child[N];
/**
* constructs a subtree with the nodes in the range [l,r] of height h
* @param l left endpoint of the range
* @param r right endpoint of the range
* @param h height of the subtree
* @return the subtree root
*/
int construct(int l, int r, int h){
if(l > r)
return 0;
int mid = (l+r) / 2;
int root;
// check if the requested height can be obtained when the mid is used as a root
if(r-mid+1 >= h)
root = mid;
else
root = r-h+1;
// get the requested height from the right child
right_child[root] = construct(root + 1, r, h - 1);
// just ensure the left child does not have a greater height than the right
left_child[root] = construct(l, root - 1, min(h - 1, root - l));
return root;
}
void get_order(int node, vector<int>& order){
order.push_back(node);
if(left_child[node] != 0)
get_order(left_child[node], order);
if(right_child[node] != 0)
get_order(right_child[node], order);
}
int main() {
int n, h;
cin >> n >> h;
// Check if the requested height can be obtained
if (h > n || (h < LOG && n > (1 << h) - 1)) {
cout << "impossible" << endl;
return 0;
}
// construct the tree
int root = construct(1, n, h);
// Generate the insertion order of the nodes
vector<int> insertion_order;
get_order(root, insertion_order);
// Output the insertion order
for (int i = 0; i < n; i++) {
cout << insertion_order[i] << " ";
}
cout << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
7 4
output:
4 1 2 3 5 6 7
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
8 3
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 1
output:
1
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
2 1
output:
impossible
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
2 2
output:
1 2
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
3 1
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
3 2
output:
2 1 3
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 3
output:
1 2 3
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
4 1
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
4 2
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 3
output:
2 1 3 4
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
4 4
output:
1 2 3 4
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
5 1
output:
impossible
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 2
output:
impossible
result:
ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
5 3
output:
3 1 2 4 5
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 4
output:
2 1 3 4 5
result:
ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
5 5
output:
1 2 3 4 5
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
200000 17
output:
impossible
result:
ok
Test #19:
score: 0
Accepted
time: 18ms
memory: 5696kb
input:
200000 18
output:
100000 50000 25000 12500 6250 3125 1562 781 390 195 97 48 24 12 6 3 1 2 4 5 9 7 8 10 11 18 15 13 14 16 17 21 19 20 22 23 36 30 27 25 26 28 29 33 31 32 34 35 42 39 37 38 40 41 45 43 44 46 47 72 60 54 51 49 50 52 53 57 55 56 58 59 66 63 61 62 64 65 69 67 68 70 71 84 78 75 73 74 76 77 81 79 80 82 83 90...
result:
ok
Test #20:
score: 0
Accepted
time: 17ms
memory: 15104kb
input:
200000 200000
output:
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 ...
result:
ok
Test #21:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
200000 1
output:
impossible
result:
ok
Test #22:
score: 0
Accepted
time: 5ms
memory: 4852kb
input:
131070 17
output:
65535 32767 16383 8191 4095 2047 1023 511 255 127 63 31 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30 47 39 35 33 32 34 37 36 38 43 41 40 42 45 44 46 55 51 49 48 50 53 52 54 59 57 56 58 61 60 62 95 79 71 67 65 64 66 69 68 70 75 73 72 74 77 76 78 87 83 81 80 82 85 8...
result:
ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
2047 11
output:
1024 512 256 128 64 32 16 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15 24 20 18 17 19 22 21 23 28 26 25 27 30 29 31 48 40 36 34 33 35 38 37 39 44 42 41 43 46 45 47 56 52 50 49 51 54 53 55 60 58 57 59 62 61 63 96 80 72 68 66 65 67 70 69 71 76 74 73 75 78 77 79 88 84 82 81 83 86 85 87 92 90 89 91 94 93 95 112 ...
result:
ok
Test #24:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
2048 11
output:
impossible
result:
ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
65537 16
output:
impossible
result:
ok
Test #26:
score: 0
Accepted
time: 4ms
memory: 4440kb
input:
65534 16
output:
32767 16383 8191 4095 2047 1023 511 255 127 63 31 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30 47 39 35 33 32 34 37 36 38 43 41 40 42 45 44 46 55 51 49 48 50 53 52 54 59 57 56 58 61 60 62 95 79 71 67 65 64 66 69 68 70 75 73 72 74 77 76 78 87 83 81 80 82 85 84 86 9...
result:
ok
Test #27:
score: 0
Accepted
time: 9ms
memory: 4284kb
input:
65535 16
output:
32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15 24 20 18 17 19 22 21 23 28 26 25 27 30 29 31 48 40 36 34 33 35 38 37 39 44 42 41 43 46 45 47 56 52 50 49 51 54 53 55 60 58 57 59 62 61 63 96 80 72 68 66 65 67 70 69 71 76 74 73 75 78 77 79 88 84 82 81 83 86 85 8...
result:
ok
Test #28:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
131072 17
output:
impossible
result:
ok
Test #29:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
16385 14
output:
impossible
result:
ok
Test #30:
score: 0
Accepted
time: 5ms
memory: 5844kb
input:
60154 37250
output:
22905 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 10...
result:
ok
Test #31:
score: 0
Accepted
time: 10ms
memory: 6620kb
input:
131517 28102
output:
65759 32879 4779 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 9...
result:
ok
Test #32:
score: 0
Accepted
time: 19ms
memory: 11800kb
input:
185570 129405
output:
56166 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 10...
result:
ok
Test #33:
score: 0
Accepted
time: 4ms
memory: 4508kb
input:
45486 4860
output:
22743 11371 5685 828 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 ...
result:
ok
Test #34:
score: 0
Accepted
time: 6ms
memory: 8144kb
input:
108591 75200
output:
33392 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 10...
result:
ok
Test #35:
score: 0
Accepted
time: 0ms
memory: 4084kb
input:
9982 6744
output:
3239 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...
result:
ok
Test #36:
score: 0
Accepted
time: 4ms
memory: 5028kb
input:
45420 16088
output:
22710 6623 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 1...
result:
ok
Test #37:
score: 0
Accepted
time: 13ms
memory: 6584kb
input:
185780 19454
output:
92890 46445 23222 3771 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 9...
result:
ok
Test #38:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
7905 6430
output:
1476 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...
result:
ok
Test #39:
score: 0
Accepted
time: 13ms
memory: 14288kb
input:
196560 181805
output:
14756 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 10...
result:
ok