ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214257 | #2022. a | KXG | 100 | 184ms | 3128kb | C++ | 1.3kb | 2024-11-16 20:47:25 | 2024-11-16 23:12:56 |
answer
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, a[100010];
vector<pair<int, int> > ans;
void sort(int l, int r, int k) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
sort(l, mid, k);
sort(mid + 1, r, k);
int lpos, rpos;
if (!((a[mid] >> k) & 1) || (a[mid + 1] >> k) & 1) {
return;
}
for (int i = mid; i >= l; i--) {
if ((a[i] >> k) & 1) {
lpos = i;
}
}
for (int i = mid + 1; i <= r; i++) {
if (!((a[i] >> k) & 1)) {
rpos = i;
}
}
ans.push_back({lpos, rpos});
reverse(a + lpos, a + rpos + 1);
return;
}
void solve(int l, int r, int k) {
if (l >= r) {
return;
}
sort(l, r, k);
if (k == 0) {
return;
}
int mid = l - 1;
for (int i = l; i <= r; i++) {
if (!((a[i] >> k) & 1)) {
mid = i;
}
}
solve(l, mid, k - 1);
solve(mid + 1, r, k - 1);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
solve(1, n, 15);
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++) {
printf("%d %d\n", ans[i].first, ans[i].second);
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1084kb
input:
63 19732 30594 10113 7702 9784 6421 4697 13517 5317 8508 26509 15653 2986 31587 11246 12158 24378 49...
output:
160 1 4 3 8 11 12 14 16 12 15 7 14 17 18 22 23 18 22 27 28 26 27 29 30 30 31 27 30 20 28 13 23 33 35...
result:
ok ok,using 585 times
Test #2:
score: 0
Accepted
time: 0ms
memory: 1084kb
input:
25 21264 13876 11861 12802 18452 3136 17660 21163 14140 20632 25998 22051 10612 12680 7873 23249 274...
output:
49 1 2 2 4 5 6 4 5 8 9 11 13 9 11 5 9 20 22 24 25 21 24 16 22 7 18 1 4 7 8 8 9 9 10 2 9 3 4 2 3 1 2 ...
result:
ok ok,using 145 times
Test #3:
score: 0
Accepted
time: 1ms
memory: 1088kb
input:
95 26373 31391 7777 12225 25301 24166 2461 4926 15751 18727 29175 18511 17455 16025 16845 6723 3477 ...
output:
278 1 3 2 4 3 9 13 14 14 17 22 23 23 24 20 23 16 21 6 18 25 26 32 33 26 32 44 45 46 47 47 48 45 47 3...
result:
ok ok,using 1063 times
Test #4:
score: 0
Accepted
time: 0ms
memory: 1088kb
input:
100 15104 1621 22502 12704 13109 9592 1390 22280 23468 26863 23084 10981 20492 7842 12883 16636 2565...
output:
278 3 4 4 7 11 12 8 11 7 8 17 18 16 17 21 22 23 24 24 25 22 24 17 23 8 20 26 28 27 31 33 34 34 35 36...
result:
ok ok,using 1105 times
Test #5:
score: 0
Accepted
time: 1ms
memory: 1088kb
input:
100 13822 19801 16537 25492 24250 30303 18588 13044 8538 23642 864 10878 16671 5509 13062 15457 2577...
output:
276 10 12 2 11 17 18 18 19 20 25 19 22 6 21 28 31 33 34 34 37 30 35 39 40 43 44 40 43 45 50 42 47 33...
result:
ok ok,using 1100 times
Subtask #2:
score: 40
Accepted
Test #6:
score: 40
Accepted
time: 0ms
memory: 1096kb
input:
197 10471 12679 10817 27406 21095 21068 9625 5396 14548 20977 29338 17674 30961 25672 4782 22715 301...
output:
613 5 7 4 5 5 9 14 15 20 21 21 22 15 21 7 16 26 27 27 29 30 32 29 30 34 35 37 38 35 37 30 36 39 41 4...
result:
ok ok,using 2733 times
Test #7:
score: 0
Accepted
time: 0ms
memory: 1108kb
input:
354 28133 31628 5619 8961 1003 9779 27591 14336 31618 17755 6349 17570 25604 24107 23136 21537 16494...
output:
1312 1 3 2 6 7 8 10 11 8 10 5 8 22 23 13 22 7 16 25 26 26 29 30 34 29 31 36 37 38 39 39 40 37 39 41 ...
result:
ok ok,using 6184 times
Test #8:
score: 0
Accepted
time: 1ms
memory: 1112kb
input:
512 14563 17808 18597 4341 12143 30490 13558 4331 30512 15302 14593 3642 21783 21775 23315 5766 1661...
output:
2039 3 4 2 3 6 8 3 7 9 10 10 12 15 16 13 15 12 13 6 12 17 18 19 20 18 19 19 22 29 31 28 29 21 28 10 ...
result:
ok ok,using 10122 times
Test #9:
score: 0
Accepted
time: 1ms
memory: 1188kb
input:
1000 1502 12015 26522 985 16804 3210 22284 28860 17265 9237 23503 15006 9625 30582 12808 25544 5298 ...
output:
4427 3 4 5 6 4 5 9 10 11 12 10 11 14 15 11 14 5 12 18 22 25 28 31 32 29 31 27 29 20 27 9 22 39 40 38...
result:
ok ok,using 24525 times
Test #10:
score: 0
Accepted
time: 1ms
memory: 1184kb
input:
1000 220 30195 7500 27597 28712 10097 25659 20392 16159 6016 31747 14902 5036 29017 31162 24365 2359...
output:
4481 2 3 5 6 3 5 11 12 12 13 4 12 17 18 19 20 18 19 21 24 19 22 25 26 26 29 21 26 8 22 43 44 41 43 4...
result:
ok ok,using 24499 times
Subtask #3:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 11ms
memory: 1680kb
input:
29160 3 3 5 5 4 4 5 1 3 2 5 1 4 3 2 3 1 2 1 5 4 4 4 0 2 3 4 2 1 4 4 5 3 3 5 4 2 4 4 1 3 5 1 1 2 2 2 ...
output:
38188 7 8 5 7 3 5 11 12 13 14 14 15 12 14 4 13 23 24 24 26 27 28 28 29 26 28 20 27 9 24 32 33 30 32 ...
result:
ok ok,using 514564 times
Test #12:
score: 0
Accepted
time: 12ms
memory: 1680kb
input:
29654 4 0 1 1 0 2 2 3 2 4 2 3 0 1 2 1 1 0 2 2 5 2 5 4 4 5 0 2 3 4 2 5 1 1 0 2 2 2 2 5 3 5 2 1 0 1 5 ...
output:
38628 1 2 2 4 4 8 10 12 12 15 8 14 21 22 23 29 22 25 14 24 30 31 32 33 31 32 32 37 40 41 42 43 43 44...
result:
ok ok,using 522943 times
Test #13:
score: 0
Accepted
time: 10ms
memory: 1396kb
input:
23759 0 4 4 5 0 0 4 2 0 2 5 4 0 1 0 1 2 3 4 1 5 1 1 2 4 2 4 3 4 3 0 3 3 3 2 2 4 1 4 3 1 4 5 1 3 2 1 ...
output:
30993 4 5 5 6 2 5 7 8 8 9 9 10 4 9 19 20 20 24 7 22 25 26 29 30 26 29 28 36 37 38 38 41 43 44 44 45 ...
result:
ok ok,using 408575 times
Test #14:
score: 0
Accepted
time: 8ms
memory: 1688kb
input:
32000 1 5 4 5 2 4 0 4 5 3 2 2 4 0 3 2 4 3 0 5 1 1 1 5 4 3 0 4 3 1 2 0 0 0 4 4 5 5 4 2 4 2 0 1 3 2 4 ...
output:
41179 6 7 2 6 9 10 10 12 13 14 14 16 12 15 4 14 17 18 18 19 19 23 25 26 26 27 27 32 22 30 10 27 39 4...
result:
ok ok,using 567288 times
Test #15:
score: 0
Accepted
time: 10ms
memory: 1692kb
input:
32000 2 5 2 0 0 2 5 2 0 0 1 2 0 5 3 4 0 1 5 2 3 4 5 3 1 5 1 4 5 2 5 0 1 4 0 1 3 0 5 2 2 2 2 5 0 1 1 ...
output:
41237 2 4 7 8 4 7 14 15 7 14 19 20 23 24 22 23 20 22 26 27 29 30 31 32 30 31 27 30 22 28 13 25 34 36...
result:
ok ok,using 567668 times
Subtask #4:
score: 10
Accepted
Test #16:
score: 10
Accepted
time: 35ms
memory: 3100kb
input:
25162 6548 134 11176 15393 24121 2053 29582 27616 22505 27930 3608 3082 22087 20841 5912 29959 21750...
output:
165559 5 6 8 12 6 9 14 15 17 18 15 17 20 22 23 25 21 23 16 21 8 17 26 27 27 30 36 38 35 36 28 35 39 ...
result:
ok ok,using 1307092 times
Test #17:
score: 0
Accepted
time: 15ms
memory: 2008kb
input:
13372 26001 8161 11243 31249 17641 3471 20342 11205 10364 6910 16562 14549 14518 1517 14171 739 2413...
output:
82532 1 2 2 3 5 6 3 5 11 14 4 13 17 18 18 20 22 24 23 27 20 25 10 23 28 29 30 31 29 30 32 33 30 32 3...
result:
ok ok,using 610381 times
Test #18:
score: 0
Accepted
time: 18ms
memory: 2032kb
input:
19761 26255 27109 5277 12037 28781 24950 6309 20913 27434 4457 25574 14446 10697 31185 14349 17737 2...
output:
127349 1 3 2 4 6 7 9 10 7 9 3 7 11 12 12 13 14 15 13 14 19 20 16 19 14 16 5 14 23 24 26 27 29 30 27 ...
result:
ok ok,using 979941 times
Test #19:
score: 0
Accepted
time: 36ms
memory: 3124kb
input:
32000 30347 31469 13058 20205 19829 2372 10241 20616 25222 30014 29774 414 1519 26519 882 14611 2885...
output:
214347 1 3 5 6 6 7 2 6 11 12 9 11 14 16 10 15 4 12 17 19 18 23 26 28 29 30 30 32 28 31 21 30 8 26 33...
result:
ok ok,using 1737836 times
Test #20:
score: 0
Accepted
time: 24ms
memory: 3128kb
input:
32000 29833 18417 7092 14816 30969 23083 28208 11380 24884 26793 6017 311 28930 24186 1060 13432 297...
output:
214149 1 4 7 8 5 7 3 5 9 12 13 16 11 14 4 12 17 18 18 19 21 22 23 24 22 23 19 22 28 31 21 30 8 26 34...
result:
ok ok,using 1736941 times