QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197850 | #3521. Insertion Order | MahmoudAtia# | AC ✓ | 23ms | 28564kb | C++14 | 1.3kb | 2023-10-02 20:52:09 | 2023-10-02 20:52:09 |
Judging History
answer
#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18;
const int N = 2e5 + 5, M = 1e5 + 5, MOD = 998244353;
#define EPS 1e-9
int n, m, sz[N], id, ord[N];
vector<int> v[N];
int dfs(int node, int lvl) {
sz[node] = 1;
while (v[node].size() < 2 && lvl < m && id < n) {
v[node].push_back(++id);
sz[node] += dfs(id, lvl + 1);
}
return sz[node];
}
void dfs2(int node, int par, int isright) {
if (isright) ord[node] = par + 1 + (v[node].size() >= 1 ? sz[v[node][0]] : 0);
else ord[node] = par - 1 - (v[node].size() >= 2 ? sz[v[node][1]] : 0);
for (int i = 0; i < v[node].size(); i++) dfs2(v[node][i], ord[node], i);
}
int main() {
// ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
id = 1;
int mn = 0;
int tmp = n;
while (tmp) tmp >>= 1, mn++;
if (m < mn) return !(cout << "impossible");
dfs(1, 1);
// for (int i = 1; i <= n; i++) {
// for (auto x:v[i]) cout << x << " ";
// cout << endl;
// }
// for (int i = 1; i <= n; i++) cout << sz[i] << " ";
// cout << endl;
dfs2(1, 0, 1);
for (int i = 1; i <= n; i++) cout << ord[i] << " ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9300kb
input:
7 4
output:
7 4 2 1 3 6 5
result:
ok
Test #2:
score: 0
Accepted
time: 2ms
memory: 8616kb
input:
8 3
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 9612kb
input:
1 1
output:
1
result:
ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 9368kb
input:
2 1
output:
impossible
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 8392kb
input:
2 2
output:
2 1
result:
ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 8948kb
input:
3 1
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 1ms
memory: 9628kb
input:
3 2
output:
2 1 3
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 8800kb
input:
3 3
output:
3 2 1
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 8920kb
input:
4 1
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 8208kb
input:
4 2
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 9388kb
input:
4 3
output:
4 2 1 3
result:
ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 8448kb
input:
4 4
output:
4 3 2 1
result:
ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 9812kb
input:
5 1
output:
impossible
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 8964kb
input:
5 2
output:
impossible
result:
ok
Test #15:
score: 0
Accepted
time: 1ms
memory: 8404kb
input:
5 3
output:
4 2 1 3 5
result:
ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 8932kb
input:
5 4
output:
5 4 2 1 3
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 9556kb
input:
5 5
output:
5 4 3 2 1
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 9084kb
input:
200000 17
output:
impossible
result:
ok
Test #19:
score: 0
Accepted
time: 10ms
memory: 13008kb
input:
200000 18
output:
131072 65536 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 ...
result:
ok
Test #20:
score: 0
Accepted
time: 23ms
memory: 28564kb
input:
200000 200000
output:
200000 199999 199998 199997 199996 199995 199994 199993 199992 199991 199990 199989 199988 199987 199986 199985 199984 199983 199982 199981 199980 199979 199978 199977 199976 199975 199974 199973 199972 199971 199970 199969 199968 199967 199966 199965 199964 199963 199962 199961 199960 199959 199958...
result:
ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 8512kb
input:
200000 1
output:
impossible
result:
ok
Test #22:
score: 0
Accepted
time: 14ms
memory: 11652kb
input:
131070 17
output:
65536 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 8...
result:
ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 8372kb
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: 2ms
memory: 9100kb
input:
2048 11
output:
impossible
result:
ok
Test #25:
score: 0
Accepted
time: 1ms
memory: 8228kb
input:
65537 16
output:
impossible
result:
ok
Test #26:
score: 0
Accepted
time: 6ms
memory: 9808kb
input:
65534 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 #27:
score: 0
Accepted
time: 3ms
memory: 10384kb
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: 8344kb
input:
131072 17
output:
impossible
result:
ok
Test #29:
score: 0
Accepted
time: 2ms
memory: 8800kb
input:
16385 14
output:
impossible
result:
ok
Test #30:
score: 0
Accepted
time: 8ms
memory: 12852kb
input:
60154 37250
output:
60154 60153 60152 60151 60150 60149 60148 60147 60146 60145 60144 60143 60142 60141 60140 60139 60138 60137 60136 60135 60134 60133 60132 60131 60130 60129 60128 60127 60126 60125 60124 60123 60122 60121 60120 60119 60118 60117 60116 60115 60114 60113 60112 60111 60110 60109 60108 60107 60106 60105 ...
result:
ok
Test #31:
score: 0
Accepted
time: 14ms
memory: 13668kb
input:
131517 28102
output:
131517 131516 131515 131514 131513 131512 131511 131510 131509 131508 131507 131506 131505 131504 131503 131502 131501 131500 131499 131498 131497 131496 131495 131494 131493 131492 131491 131490 131489 131488 131487 131486 131485 131484 131483 131482 131481 131480 131479 131478 131477 131476 131475...
result:
ok
Test #32:
score: 0
Accepted
time: 19ms
memory: 22856kb
input:
185570 129405
output:
185570 185569 185568 185567 185566 185565 185564 185563 185562 185561 185560 185559 185558 185557 185556 185555 185554 185553 185552 185551 185550 185549 185548 185547 185546 185545 185544 185543 185542 185541 185540 185539 185538 185537 185536 185535 185534 185533 185532 185531 185530 185529 185528...
result:
ok
Test #33:
score: 0
Accepted
time: 6ms
memory: 10508kb
input:
45486 4860
output:
45486 45485 45484 45483 45482 45481 45480 45479 45478 45477 45476 45475 45474 45473 45472 45471 45470 45469 45468 45467 45466 45465 45464 45463 45462 45461 45460 45459 45458 45457 45456 45455 45454 45453 45452 45451 45450 45449 45448 45447 45446 45445 45444 45443 45442 45441 45440 45439 45438 45437 ...
result:
ok
Test #34:
score: 0
Accepted
time: 10ms
memory: 17036kb
input:
108591 75200
output:
108591 108590 108589 108588 108587 108586 108585 108584 108583 108582 108581 108580 108579 108578 108577 108576 108575 108574 108573 108572 108571 108570 108569 108568 108567 108566 108565 108564 108563 108562 108561 108560 108559 108558 108557 108556 108555 108554 108553 108552 108551 108550 108549...
result:
ok
Test #35:
score: 0
Accepted
time: 3ms
memory: 10464kb
input:
9982 6744
output:
9982 9981 9980 9979 9978 9977 9976 9975 9974 9973 9972 9971 9970 9969 9968 9967 9966 9965 9964 9963 9962 9961 9960 9959 9958 9957 9956 9955 9954 9953 9952 9951 9950 9949 9948 9947 9946 9945 9944 9943 9942 9941 9940 9939 9938 9937 9936 9935 9934 9933 9932 9931 9930 9929 9928 9927 9926 9925 9924 9923 ...
result:
ok
Test #36:
score: 0
Accepted
time: 6ms
memory: 10728kb
input:
45420 16088
output:
45420 45419 45418 45417 45416 45415 45414 45413 45412 45411 45410 45409 45408 45407 45406 45405 45404 45403 45402 45401 45400 45399 45398 45397 45396 45395 45394 45393 45392 45391 45390 45389 45388 45387 45386 45385 45384 45383 45382 45381 45380 45379 45378 45377 45376 45375 45374 45373 45372 45371 ...
result:
ok
Test #37:
score: 0
Accepted
time: 14ms
memory: 14204kb
input:
185780 19454
output:
185780 185779 185778 185777 185776 185775 185774 185773 185772 185771 185770 185769 185768 185767 185766 185765 185764 185763 185762 185761 185760 185759 185758 185757 185756 185755 185754 185753 185752 185751 185750 185749 185748 185747 185746 185745 185744 185743 185742 185741 185740 185739 185738...
result:
ok
Test #38:
score: 0
Accepted
time: 0ms
memory: 9652kb
input:
7905 6430
output:
7905 7904 7903 7902 7901 7900 7899 7898 7897 7896 7895 7894 7893 7892 7891 7890 7889 7888 7887 7886 7885 7884 7883 7882 7881 7880 7879 7878 7877 7876 7875 7874 7873 7872 7871 7870 7869 7868 7867 7866 7865 7864 7863 7862 7861 7860 7859 7858 7857 7856 7855 7854 7853 7852 7851 7850 7849 7848 7847 7846 ...
result:
ok
Test #39:
score: 0
Accepted
time: 19ms
memory: 27160kb
input:
196560 181805
output:
196560 196559 196558 196557 196556 196555 196554 196553 196552 196551 196550 196549 196548 196547 196546 196545 196544 196543 196542 196541 196540 196539 196538 196537 196536 196535 196534 196533 196532 196531 196530 196529 196528 196527 196526 196525 196524 196523 196522 196521 196520 196519 196518...
result:
ok