QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225185#3521. Insertion Orderhagry#AC ✓12ms8328kbC++141.8kb2023-10-24 04:02:352023-10-24 04:02:36

Judging History

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

  • [2023-10-24 04:02:36]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:8328kb
  • [2023-10-24 04:02:35]
  • 提交

answer

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define MP make_pair
#define all(x) x.begin(),x.end()
#define Hagry 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 l[N], r[N], p[N], d[N], h[N], curH;

int build(int lt, int rt, int par) {
    if (lt > rt)return -1;
    int root = (lt + rt + 1) / 2;

    p[root] = par;
    d[root] = d[par] + 1;

    l[root] = build(lt, root - 1, root);
    r[root] = build(root + 1, rt, root);

    h[root] = max(h[l[root]], h[r[root]]) + 1;
    return root;
}

vi BFS(int root) {
    vi res;

    queue<int> q;
    q.push(root);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        res.pb(cur);
        if (~l[cur])
            q.push(l[cur]);
        if (~r[cur])
            q.push(r[cur]);
    }
    return res;
}

void TC() {
    int n, k;
    cin >> n >> k;

    int root = build(1, n, 0);
    curH = h[root];
    if (curH > k) {
        cout << "impossible";
        return;
    }
    if(curH == k){
        vi ans = BFS(root);
        for(auto e:ans)
            cout << e << " ";
        return;
    }

    for(int i=k; i>=1; --i)
        cout << i << " ";
    if(k == n)return;
    root = build(k+1, n, k);
    vi restAns = BFS(root);
    for(auto e:restAns)
        cout << e << " ";
}

int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    Hagry
    int t = 1;
//    cin >> t;
    while (t--) {
        TC();
        cout << '\n';
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5672kb

input:

7 4

output:

4 3 2 1 6 5 7 

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

8 3

output:

impossible

result:

ok 

Test #3:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

1 1

output:

1 

result:

ok 

Test #4:

score: 0
Accepted
time: 0ms
memory: 5900kb

input:

2 1

output:

impossible

result:

ok 

Test #5:

score: 0
Accepted
time: 1ms
memory: 5876kb

input:

2 2

output:

2 1 

result:

ok 

Test #6:

score: 0
Accepted
time: 1ms
memory: 5696kb

input:

3 1

output:

impossible

result:

ok 

Test #7:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

3 2

output:

2 1 3 

result:

ok 

Test #8:

score: 0
Accepted
time: 0ms
memory: 5704kb

input:

3 3

output:

3 2 1 

result:

ok 

Test #9:

score: 0
Accepted
time: 0ms
memory: 5896kb

input:

4 1

output:

impossible

result:

ok 

Test #10:

score: 0
Accepted
time: 0ms
memory: 5728kb

input:

4 2

output:

impossible

result:

ok 

Test #11:

score: 0
Accepted
time: 0ms
memory: 5636kb

input:

4 3

output:

3 2 4 1 

result:

ok 

Test #12:

score: 0
Accepted
time: 0ms
memory: 5940kb

input:

4 4

output:

4 3 2 1 

result:

ok 

Test #13:

score: 0
Accepted
time: 0ms
memory: 5876kb

input:

5 1

output:

impossible

result:

ok 

Test #14:

score: 0
Accepted
time: 0ms
memory: 5672kb

input:

5 2

output:

impossible

result:

ok 

Test #15:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

5 3

output:

3 2 5 1 4 

result:

ok 

Test #16:

score: 0
Accepted
time: 0ms
memory: 5692kb

input:

5 4

output:

4 3 2 1 5 

result:

ok 

Test #17:

score: 0
Accepted
time: 0ms
memory: 5864kb

input:

5 5

output:

5 4 3 2 1 

result:

ok 

Test #18:

score: 0
Accepted
time: 2ms
memory: 7548kb

input:

200000 17

output:

impossible

result:

ok 

Test #19:

score: 0
Accepted
time: 8ms
memory: 8300kb

input:

200000 18

output:

100001 50001 150001 25001 75001 125001 175001 12501 37501 62501 87501 112501 137501 162501 187501 6251 18751 31251 43751 56251 68751 81251 93751 106251 118751 131251 143751 156251 168751 181251 193751 3126 9376 15626 21876 28126 34376 40626 46876 53126 59376 65626 71876 78126 84376 90626 96876 10312...

result:

ok 

Test #20:

score: 0
Accepted
time: 11ms
memory: 7496kb

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: 2ms
memory: 7556kb

input:

200000 1

output:

impossible

result:

ok 

Test #22:

score: 0
Accepted
time: 8ms
memory: 7384kb

input:

131070 17

output:

65536 32768 98304 16384 49152 81920 114688 8192 24576 40960 57344 73728 90112 106496 122880 4096 12288 20480 28672 36864 45056 53248 61440 69632 77824 86016 94208 102400 110592 118784 126976 2048 6144 10240 14336 18432 22528 26624 30720 34816 38912 43008 47104 51200 55296 59392 63488 67584 71680 757...

result:

ok 

Test #23:

score: 0
Accepted
time: 1ms
memory: 5700kb

input:

2047 11

output:

1024 512 1536 256 768 1280 1792 128 384 640 896 1152 1408 1664 1920 64 192 320 448 576 704 832 960 1088 1216 1344 1472 1600 1728 1856 1984 32 96 160 224 288 352 416 480 544 608 672 736 800 864 928 992 1056 1120 1184 1248 1312 1376 1440 1504 1568 1632 1696 1760 1824 1888 1952 2016 16 48 80 112 144 17...

result:

ok 

Test #24:

score: 0
Accepted
time: 1ms
memory: 5668kb

input:

2048 11

output:

impossible

result:

ok 

Test #25:

score: 0
Accepted
time: 1ms
memory: 5108kb

input:

65537 16

output:

impossible

result:

ok 

Test #26:

score: 0
Accepted
time: 4ms
memory: 6296kb

input:

65534 16

output:

32768 16384 49152 8192 24576 40960 57344 4096 12288 20480 28672 36864 45056 53248 61440 2048 6144 10240 14336 18432 22528 26624 30720 34816 38912 43008 47104 51200 55296 59392 63488 1024 3072 5120 7168 9216 11264 13312 15360 17408 19456 21504 23552 25600 27648 29696 31744 33792 35840 37888 39936 419...

result:

ok 

Test #27:

score: 0
Accepted
time: 4ms
memory: 5320kb

input:

65535 16

output:

32768 16384 49152 8192 24576 40960 57344 4096 12288 20480 28672 36864 45056 53248 61440 2048 6144 10240 14336 18432 22528 26624 30720 34816 38912 43008 47104 51200 55296 59392 63488 1024 3072 5120 7168 9216 11264 13312 15360 17408 19456 21504 23552 25600 27648 29696 31744 33792 35840 37888 39936 419...

result:

ok 

Test #28:

score: 0
Accepted
time: 0ms
memory: 6900kb

input:

131072 17

output:

impossible

result:

ok 

Test #29:

score: 0
Accepted
time: 1ms
memory: 3924kb

input:

16385 14

output:

impossible

result:

ok 

Test #30:

score: 0
Accepted
time: 5ms
memory: 6260kb

input:

60154 37250

output:

37250 37249 37248 37247 37246 37245 37244 37243 37242 37241 37240 37239 37238 37237 37236 37235 37234 37233 37232 37231 37230 37229 37228 37227 37226 37225 37224 37223 37222 37221 37220 37219 37218 37217 37216 37215 37214 37213 37212 37211 37210 37209 37208 37207 37206 37205 37204 37203 37202 37201 ...

result:

ok 

Test #31:

score: 0
Accepted
time: 4ms
memory: 7220kb

input:

131517 28102

output:

28102 28101 28100 28099 28098 28097 28096 28095 28094 28093 28092 28091 28090 28089 28088 28087 28086 28085 28084 28083 28082 28081 28080 28079 28078 28077 28076 28075 28074 28073 28072 28071 28070 28069 28068 28067 28066 28065 28064 28063 28062 28061 28060 28059 28058 28057 28056 28055 28054 28053 ...

result:

ok 

Test #32:

score: 0
Accepted
time: 7ms
memory: 7416kb

input:

185570 129405

output:

129405 129404 129403 129402 129401 129400 129399 129398 129397 129396 129395 129394 129393 129392 129391 129390 129389 129388 129387 129386 129385 129384 129383 129382 129381 129380 129379 129378 129377 129376 129375 129374 129373 129372 129371 129370 129369 129368 129367 129366 129365 129364 129363...

result:

ok 

Test #33:

score: 0
Accepted
time: 4ms
memory: 6532kb

input:

45486 4860

output:

4860 4859 4858 4857 4856 4855 4854 4853 4852 4851 4850 4849 4848 4847 4846 4845 4844 4843 4842 4841 4840 4839 4838 4837 4836 4835 4834 4833 4832 4831 4830 4829 4828 4827 4826 4825 4824 4823 4822 4821 4820 4819 4818 4817 4816 4815 4814 4813 4812 4811 4810 4809 4808 4807 4806 4805 4804 4803 4802 4801 ...

result:

ok 

Test #34:

score: 0
Accepted
time: 0ms
memory: 7216kb

input:

108591 75200

output:

75200 75199 75198 75197 75196 75195 75194 75193 75192 75191 75190 75189 75188 75187 75186 75185 75184 75183 75182 75181 75180 75179 75178 75177 75176 75175 75174 75173 75172 75171 75170 75169 75168 75167 75166 75165 75164 75163 75162 75161 75160 75159 75158 75157 75156 75155 75154 75153 75152 75151 ...

result:

ok 

Test #35:

score: 0
Accepted
time: 1ms
memory: 5784kb

input:

9982 6744

output:

6744 6743 6742 6741 6740 6739 6738 6737 6736 6735 6734 6733 6732 6731 6730 6729 6728 6727 6726 6725 6724 6723 6722 6721 6720 6719 6718 6717 6716 6715 6714 6713 6712 6711 6710 6709 6708 6707 6706 6705 6704 6703 6702 6701 6700 6699 6698 6697 6696 6695 6694 6693 6692 6691 6690 6689 6688 6687 6686 6685 ...

result:

ok 

Test #36:

score: 0
Accepted
time: 3ms
memory: 6556kb

input:

45420 16088

output:

16088 16087 16086 16085 16084 16083 16082 16081 16080 16079 16078 16077 16076 16075 16074 16073 16072 16071 16070 16069 16068 16067 16066 16065 16064 16063 16062 16061 16060 16059 16058 16057 16056 16055 16054 16053 16052 16051 16050 16049 16048 16047 16046 16045 16044 16043 16042 16041 16040 16039 ...

result:

ok 

Test #37:

score: 0
Accepted
time: 12ms
memory: 8328kb

input:

185780 19454

output:

19454 19453 19452 19451 19450 19449 19448 19447 19446 19445 19444 19443 19442 19441 19440 19439 19438 19437 19436 19435 19434 19433 19432 19431 19430 19429 19428 19427 19426 19425 19424 19423 19422 19421 19420 19419 19418 19417 19416 19415 19414 19413 19412 19411 19410 19409 19408 19407 19406 19405 ...

result:

ok 

Test #38:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

7905 6430

output:

6430 6429 6428 6427 6426 6425 6424 6423 6422 6421 6420 6419 6418 6417 6416 6415 6414 6413 6412 6411 6410 6409 6408 6407 6406 6405 6404 6403 6402 6401 6400 6399 6398 6397 6396 6395 6394 6393 6392 6391 6390 6389 6388 6387 6386 6385 6384 6383 6382 6381 6380 6379 6378 6377 6376 6375 6374 6373 6372 6371 ...

result:

ok 

Test #39:

score: 0
Accepted
time: 7ms
memory: 7540kb

input:

196560 181805

output:

181805 181804 181803 181802 181801 181800 181799 181798 181797 181796 181795 181794 181793 181792 181791 181790 181789 181788 181787 181786 181785 181784 181783 181782 181781 181780 181779 181778 181777 181776 181775 181774 181773 181772 181771 181770 181769 181768 181767 181766 181765 181764 181763...

result:

ok