QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197984 | #3521. Insertion Order | beshoyhany# | AC ✓ | 10ms | 4220kb | C++20 | 2.0kb | 2023-10-02 23:10:05 | 2023-10-02 23:10:06 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll
using namespace std;
void Drakon() {
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
}
unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25;
ll gcd(ll x, ll y) {
return y ? gcd(y, x % y) : x;
}
ll lcm(ll a, ll b) {
return (a * b) / __gcd(a, b);
}
ll mul(const ll &a, const ll &b) {
return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}
ll add(const ll &a, const ll &b) {
return (a + b + 2 * MOD) % MOD;
}
ll pw(ll x, ll y) {
ll ret = 1;
while (y > 0) {
if (y % 2 == 0) {
x = mul(x, x);
y = y / 2;
} else {
ret = mul(ret, x);
y = y - 1;
}
}
return ret;
}
int n, k, mnDep;
vector<int> ans;
void calcMin(int l, int r, int dep) {
if (l > r)return;
mnDep = max(mnDep, dep);
int mid = (l + r) / 2;
ans.pp(mid);
calcMin(l, mid - 1, dep + 1);
calcMin(mid + 1, r, dep + 1);
}
void calc(int l, int r, int dep) {
if (l > r)return;
assert(dep <= k);
int mid = (l + r) / 2;
ans.pp(mid);
calc(l, mid - 1, dep + 1);
calc(mid + 1, r, dep + 1);
}
void solve() {
cin >> n >> k;
calcMin(1, n, 1);
if (k < mnDep) {
cout << "impossible";
return;
}
else if (k > mnDep) {
ans.clear();
for (int i = k; i >= 1; --i) {
ans.pp(i);
}
calc(k + 1, n, 2);
}
for (auto x: ans)cout << x << " ";
}
signed main() {
Drakon();
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:
4 3 2 1 6 5 7
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
8 3
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 1
output:
1
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 1
output:
impossible
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 2
output:
1 2
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 1
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 2
output:
2 1 3
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 3
output:
3 2 1
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 1
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4 2
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
4 3
output:
2 1 3 4
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 4
output:
4 3 2 1
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 1
output:
impossible
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 2
output:
impossible
result:
ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
5 3
output:
3 1 2 4 5
result:
ok
Test #16:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
5 4
output:
4 3 2 1 5
result:
ok
Test #17:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 5
output:
5 4 3 2 1
result:
ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 4184kb
input:
200000 17
output:
impossible
result:
ok
Test #19:
score: 0
Accepted
time: 7ms
memory: 4128kb
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: 7ms
memory: 4200kb
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: 1ms
memory: 4124kb
input:
200000 1
output:
impossible
result:
ok
Test #22:
score: 0
Accepted
time: 7ms
memory: 3968kb
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: 3676kb
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: 3712kb
input:
2048 11
output:
impossible
result:
ok
Test #25:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
65537 16
output:
impossible
result:
ok
Test #26:
score: 0
Accepted
time: 4ms
memory: 3696kb
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: 3820kb
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: 1ms
memory: 3860kb
input:
131072 17
output:
impossible
result:
ok
Test #29:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
16385 14
output:
impossible
result:
ok
Test #30:
score: 0
Accepted
time: 3ms
memory: 3772kb
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: 3ms
memory: 4220kb
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: 10ms
memory: 4172kb
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: 3ms
memory: 3748kb
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: 7ms
memory: 3772kb
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: 3824kb
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: 3720kb
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: 7ms
memory: 4184kb
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: 3684kb
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: 4208kb
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