QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#198053 | #3521. Insertion Order | Gamal74# | AC ✓ | 10ms | 3728kb | C++20 | 1.7kb | 2023-10-03 00:24:33 | 2023-10-03 00:24:33 |
Judging History
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