UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214257#2022. aKXG100184ms3128kbC++1.3kb2024-11-16 20:47:252024-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