QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198053#3521. Insertion OrderGamal74#AC ✓10ms3728kbC++201.7kb2023-10-03 00:24:332023-10-03 00:24:33

Judging History

This is the latest submission verdict.

  • [2023-10-03 00:24:33]
  • Judged
  • Verdict: AC
  • Time: 10ms
  • Memory: 3728kb
  • [2023-10-03 00:24:33]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define endl '\n'
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl

void Gamal() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};

const double EPS = 1e-9;
const ll OO = 0X3F3F3F3F3F3F3F3F;
const int N = 2e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;

void slv(int l, int r) {
    if (l > r)return;
    int mid = (l + r) / 2;
    cout << mid << ' ';
    slv(l, mid - 1);
    slv(mid + 1, r);
}

void calc(int l, int r, int k) {
    if (l > r)return;
    int sz = r - l + 1;
    if (k == sz) {
        cout << l << ' ';
        calc(l + 1, r, k - 1);
        return;
    }
    int last = 0;
    for (int i = 1; i <= sz; ++i) {
        if (__lg(i) + 1 + (sz - i) >= k) {
            last = i;
        }
    }
    slv(l, last + l - 1);
    k -= __lg(last) + 1;
    calc(l + last, r, k);
}

void solve() {
    int n, k;
    cin >> n >> k;
    int l = __lg(n) + 1;
    if (k < l) {
        cout << "impossible";
        return;
    }
    calc(1, n, k);
}


signed main() {
    Gamal();
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3648kb

input:

7 4

output:

3 1 2 5 4 6 7 

result:

ok 

Test #2:

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

input:

8 3

output:

impossible

result:

ok 

Test #3:

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

input:

1 1

output:

1 

result:

ok 

Test #4:

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

input:

2 1

output:

impossible

result:

ok 

Test #5:

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

input:

2 2

output:

1 2 

result:

ok 

Test #6:

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

input:

3 1

output:

impossible

result:

ok 

Test #7:

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

input:

3 2

output:

2 1 3 

result:

ok 

Test #8:

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

input:

3 3

output:

1 2 3 

result:

ok 

Test #9:

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

input:

4 1

output:

impossible

result:

ok 

Test #10:

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

input:

4 2

output:

impossible

result:

ok 

Test #11:

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

input:

4 3

output:

2 1 3 4 

result:

ok 

Test #12:

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

input:

4 4

output:

1 2 3 4 

result:

ok 

Test #13:

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

input:

5 1

output:

impossible

result:

ok 

Test #14:

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

input:

5 2

output:

impossible

result:

ok 

Test #15:

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

input:

5 3

output:

3 1 2 4 5 

result:

ok 

Test #16:

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

input:

5 4

output:

2 1 3 4 5 

result:

ok 

Test #17:

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

input:

5 5

output:

1 2 3 4 5 

result:

ok 

Test #18:

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

input:

200000 17

output:

impossible

result:

ok 

Test #19:

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

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: 3636kb

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: 3588kb

input:

200000 1

output:

impossible

result:

ok 

Test #22:

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

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: 3588kb

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: 3644kb

input:

2048 11

output:

impossible

result:

ok 

Test #25:

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

input:

65537 16

output:

impossible

result:

ok 

Test #26:

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

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: 3ms
memory: 3652kb

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: 3648kb

input:

131072 17

output:

impossible

result:

ok 

Test #29:

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

input:

16385 14

output:

impossible

result:

ok 

Test #30:

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

input:

60154 37250

output:

11460 5730 2865 1432 716 358 179 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 134 111 1...

result:

ok 

Test #31:

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

input:

131517 28102

output:

51716 25858 12929 6464 3232 1616 808 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...

result:

ok 

Test #32:

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

input:

185570 129405

output:

28091 14045 7022 3511 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 85 87...

result:

ok 

Test #33:

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

input:

45486 4860

output:

20321 10160 5080 2540 1270 635 317 158 79 39 19 9 4 2 1 3 6 5 7 8 14 11 10 12 13 16 15 17 18 29 24 21 20 22 23 26 25 27 28 34 31 30 32 33 36 35 37 38 59 49 44 41 40 42 43 46 45 47 48 54 51 50 52 53 56 55 57 58 69 64 61 60 62 63 66 65 67 68 74 71 70 72 73 76 75 77 78 118 98 88 83 81 80 82 85 84 86 87...

result:

ok 

Test #34:

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

input:

108591 75200

output:

16704 8352 4176 2088 1044 522 261 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 86 88 9...

result:

ok 

Test #35:

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

input:

9982 6744

output:

1625 812 406 203 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 97 95 ...

result:

ok 

Test #36:

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

input:

45420 16088

output:

14674 7337 3668 1834 917 458 229 114 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 85 71 64 60 58 59 62 61 63 67 65 66 69 68 70 78 74 72 73 76 75 77 81 79 80 83 82 84 99 92 88 86 87 90...

result:

ok 

Test #37:

score: 0
Accepted
time: 9ms
memory: 3592kb

input:

185780 19454

output:

83172 41586 20793 10396 5198 2599 1299 649 324 162 81 40 20 10 5 2 1 3 4 7 6 8 9 15 12 11 13 14 17 16 18 19 30 25 22 21 23 24 27 26 28 29 35 32 31 33 34 37 36 38 39 60 50 45 42 41 43 44 47 46 48 49 55 52 51 53 54 57 56 58 59 70 65 62 61 63 64 67 66 68 69 75 72 71 73 74 78 76 77 79 80 121 101 91 86 8...

result:

ok 

Test #38:

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

input:

7905 6430

output:

743 371 185 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 94 93 ...

result:

ok 

Test #39:

score: 0
Accepted
time: 10ms
memory: 3652kb

input:

196560 181805

output:

7385 3692 1846 923 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 88 91 9...

result:

ok