QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#225170#3521. Insertion Ordergondozu#AC ✓14ms12076kbC++141.3kb2023-10-24 02:15:362023-10-24 02:15:36

Judging History

你现在查看的是最新测评结果

  • [2023-10-24 02:15:36]
  • 评测
  • 测评结果:AC
  • 用时:14ms
  • 内存:12076kb
  • [2023-10-24 02:15:36]
  • 提交

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