QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#225170 | #3521. Insertion Order | gondozu# | AC ✓ | 14ms | 12076kb | C++14 | 1.3kb | 2023-10-24 02:15:36 | 2023-10-24 02:15:36 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define Gondozu ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector <pair<int, int>>;
using vvi = vector <vector<int>>;
const int OO = 1e9 + 5;
const int N = 2e5 + 5;
int lc[N], rc[N];
int slv(int l ,int r, int h){
if(l>r)
return 0;
int mid = (l+r)/2, root;
if(h == -1 || r-mid+1 >= h)
root = mid;
else
root = r-h+1;
rc[root] = slv(root+1,r,h-1);
lc[root] = slv(l,root-1,-1);
return root;
}
vi ans;
void dfs(int v){
ans.pb(v);
if(lc[v])
dfs(lc[v]);
if(rc[v])
dfs(rc[v]);
}
void TC()
{
int n, k;
cin >> n >> k;
if(k > n || k < (int)log2(n)+1)
return void(cout << "impossible");
int root = slv(1,n,k);
dfs(root);
for(int i : ans) cout << i << ' ';
}
int32_t main() {
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#endif
Gondozu
int t = 1;
// cin >> t;
while (t--) {
TC();
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
7 4
output:
4 2 1 3 5 6 7
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
8 3
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
1 1
output:
1
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
2 1
output:
impossible
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
2 2
output:
1 2
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 1
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
3 2
output:
2 1 3
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
3 3
output:
1 2 3
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
4 1
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
4 2
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
4 3
output:
2 1 3 4
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
4 4
output:
1 2 3 4
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
5 1
output:
impossible
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
5 2
output:
impossible
result:
ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
5 3
output:
3 1 2 4 5
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
5 4
output:
2 1 3 4 5
result:
ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
5 5
output:
1 2 3 4 5
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
200000 17
output:
impossible
result:
ok
Test #19:
score: 0
Accepted
time: 3ms
memory: 5848kb
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: 10ms
memory: 12076kb
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: 3736kb
input:
200000 1
output:
impossible
result:
ok
Test #22:
score: 0
Accepted
time: 3ms
memory: 5120kb
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: 1ms
memory: 3648kb
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: 3740kb
input:
2048 11
output:
impossible
result:
ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
65537 16
output:
impossible
result:
ok
Test #26:
score: 0
Accepted
time: 4ms
memory: 4356kb
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: 4ms
memory: 4384kb
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: 3676kb
input:
131072 17
output:
impossible
result:
ok
Test #29:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
16385 14
output:
impossible
result:
ok
Test #30:
score: 0
Accepted
time: 4ms
memory: 5484kb
input:
60154 37250
output:
22905 11452 5726 2863 1431 715 357 178 89 44 22 11 5 2 1 3 4 8 6 7 9 10 16 13 12 14 15 19 17 18 20 21 33 27 24 23 25 26 30 28 29 31 32 38 35 34 36 37 41 39 40 42 43 66 55 49 46 45 47 48 52 50 51 53 54 60 57 56 58 59 63 61 62 64 65 77 71 68 67 69 70 74 72 73 75 76 83 80 78 79 81 82 86 84 85 87 88 133...
result:
ok
Test #31:
score: 0
Accepted
time: 8ms
memory: 6260kb
input:
131517 28102
output:
65759 32879 16439 8219 4109 2054 1027 513 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 #32:
score: 0
Accepted
time: 8ms
memory: 9640kb
input:
185570 129405
output:
56166 28083 14041 7020 3510 1755 877 438 219 109 54 27 13 6 3 1 2 4 5 9 7 8 11 10 12 20 16 14 15 18 17 19 23 21 22 25 24 26 40 33 30 28 29 31 32 36 34 35 38 37 39 47 43 41 42 45 44 46 50 48 49 52 51 53 81 67 60 57 55 56 58 59 63 61 62 65 64 66 74 70 68 69 72 71 73 77 75 76 79 78 80 95 88 84 82 83 86...
result:
ok
Test #33:
score: 0
Accepted
time: 3ms
memory: 4424kb
input:
45486 4860
output:
22743 11371 5685 2842 1421 710 355 177 88 44 22 11 5 2 1 3 4 8 6 7 9 10 16 13 12 14 15 19 17 18 20 21 33 27 24 23 25 26 30 28 29 31 32 38 35 34 36 37 41 39 40 42 43 66 55 49 46 45 47 48 52 50 51 53 54 60 57 56 58 59 63 61 62 64 65 77 71 68 67 69 70 74 72 73 75 76 82 79 78 80 81 85 83 84 86 87 132 11...
result:
ok
Test #34:
score: 0
Accepted
time: 7ms
memory: 7072kb
input:
108591 75200
output:
33392 16696 8348 4174 2087 1043 521 260 130 65 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 64 97 81 73 69 67 66 68 71 70 72 77 75 74 76 79 78 80 89 85 83 82 84 87 8...
result:
ok
Test #35:
score: 0
Accepted
time: 1ms
memory: 4132kb
input:
9982 6744
output:
3239 1619 809 404 202 101 50 25 12 6 3 1 2 4 5 9 7 8 10 11 18 15 13 14 16 17 21 19 20 23 22 24 37 31 28 26 27 29 30 34 32 33 35 36 43 40 38 39 41 42 46 44 45 48 47 49 75 62 56 53 51 52 54 55 59 57 58 60 61 68 65 63 64 66 67 71 69 70 73 72 74 88 81 78 76 77 79 80 84 82 83 86 85 87 94 91 89 90 92 93 9...
result:
ok
Test #36:
score: 0
Accepted
time: 3ms
memory: 4708kb
input:
45420 16088
output:
22710 11355 5677 2838 1419 709 354 177 88 44 22 11 5 2 1 3 4 8 6 7 9 10 16 13 12 14 15 19 17 18 20 21 33 27 24 23 25 26 30 28 29 31 32 38 35 34 36 37 41 39 40 42 43 66 55 49 46 45 47 48 52 50 51 53 54 60 57 56 58 59 63 61 62 64 65 77 71 68 67 69 70 74 72 73 75 76 82 79 78 80 81 85 83 84 86 87 132 11...
result:
ok
Test #37:
score: 0
Accepted
time: 11ms
memory: 6292kb
input:
185780 19454
output:
92890 46445 23222 11611 5805 2902 1451 725 362 181 90 45 22 11 5 2 1 3 4 8 6 7 9 10 16 13 12 14 15 19 17 18 20 21 33 27 24 23 25 26 30 28 29 31 32 39 36 34 35 37 38 42 40 41 43 44 67 56 50 47 46 48 49 53 51 52 54 55 61 58 57 59 60 64 62 63 65 66 78 72 69 68 70 71 75 73 74 76 77 84 81 79 80 82 83 87 ...
result:
ok
Test #38:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
7905 6430
output:
1476 738 369 184 92 46 23 11 5 2 1 3 4 8 6 7 9 10 17 14 12 13 15 16 20 18 19 21 22 34 28 25 24 26 27 31 29 30 32 33 40 37 35 36 38 39 43 41 42 44 45 69 57 51 48 47 49 50 54 52 53 55 56 63 60 58 59 61 62 66 64 65 67 68 80 74 71 70 72 73 77 75 76 78 79 86 83 81 82 84 85 89 87 88 90 91 138 115 103 97 9...
result:
ok
Test #39:
score: 0
Accepted
time: 14ms
memory: 11456kb
input:
196560 181805
output:
14756 7378 3689 1844 922 461 230 115 57 28 14 7 3 1 2 5 4 6 10 8 9 12 11 13 21 17 15 16 19 18 20 24 22 23 26 25 27 42 35 31 29 30 33 32 34 38 36 37 40 39 41 49 45 43 44 47 46 48 53 51 50 52 55 54 56 86 71 64 60 58 59 62 61 63 67 65 66 69 68 70 78 74 72 73 76 75 77 82 80 79 81 84 83 85 100 93 89 87 8...
result:
ok