UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#170430#32. Sortljc20020730901552ms2144kbC++1003b2023-04-28 16:27:582023-04-28 16:27:58

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> pii;
pii a[N];
int pos[N];
int stdd;
void merge(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    merge(l, mid);
    merge(mid + 1, r);
    int L = mid, R = mid;
    int i = mid, j = mid + 1;
    while (i >= l && pos[i] > stdd) L = i--;
    while (j <= r && pos[j] <= stdd) R = j++;
    if (L != R) {
        cout << L << " " << R << endl;
        reverse(pos + L, pos + R + 1);
    }
}
void mergeSort(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    stdd = mid;
    merge(l, r);
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
}
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        pos[a[i].second] = i;
    }
    mergeSort(1, n);
    cout << "-1 -1" << endl;
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

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

input:

5
0 0 0 1 1

output:

1 2
2 3
2 3
1 2
-1 -1

result:

ok Correct.

Test #2:

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

input:

5
716816476 646500411 807499637 544792531 128057616

output:

1 2
4 5
2 5
1 2
2 3
1 2
4 5
-1 -1

result:

ok Correct.

Test #3:

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

input:

7
0 0 1 0 0 0 0

output:

1 2
3 4
2 3
4 5
2 3
1 2
5 6
6 7
-1 -1

result:

ok Correct.

Test #4:

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

input:

7
685386610 762888212 32009424 450956771 498508039 313999604 331164353

output:

3 4
1 4
5 6
6 7
3 6
3 4
2 3
3 4
6 7
5 6
-1 -1

result:

ok Correct.

Test #5:

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

input:

10
1 1 0 0 0 0 0 1 1 1

output:

1 3
4 5
2 5
6 7
4 7
1 2
2 3
2 3
1 2
6 7
7 8
7 8
-1 -1

result:

ok Correct.

Test #6:

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

input:

10
552474873 603523889 451688250 856980678 746716186 316583031 509750159 895158422 895128023 276991286

output:

2 3
6 7
9 10
8 9
3 8
1 2
2 3
3 4
1 2
2 3
4 5
6 7
7 8
6 7
7 8
9 10
-1 -1

result:

ok Correct.

Test #7:

score: 5
Accepted
time: 28ms
memory: 2000kb

input:

3000
774135042 955379290 425485912 951649655 435211761 517813461 22865164 126834432 859390051 751505...

output:

1 3
4 5
2 4
7 8
10 11
3 8
13 14
14 16
19 20
20 22
15 20
5 16
25 26
28 30
26 28
31 32
34 35
35 36
32 ...

result:

ok Correct.

Test #8:

score: 5
Accepted
time: 16ms
memory: 2004kb

input:

4000
0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 1 1...

output:

3 4
2 4
5 6
7 8
6 8
4 7
9 10
11 12
10 12
13 14
12 13
7 13
17 18
19 20
18 19
21 22
23 24
22 23
20 23
...

result:

ok Correct.

Test #9:

score: 5
Accepted
time: 24ms
memory: 2004kb

input:

4000
253876655 192406499 33773493 714588720 62247300 512617285 830025704 158991275 146203174 6211898...

output:

1 2
2 3
7 8
6 7
4 6
11 12
10 12
13 14
15 16
14 15
12 14
6 13
17 18
19 20
18 19
21 22
23 24
22 23
20 ...

result:

ok Correct.

Test #10:

score: 5
Accepted
time: 43ms
memory: 2012kb

input:

5000
0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1...

output:

2 3
4 5
3 5
6 7
9 10
8 9
5 8
11 12
12 13
14 15
13 14
16 17
15 17
8 16
21 22
24 25
22 24
26 27
29 30
...

result:

ok Correct.

Test #11:

score: 5
Accepted
time: 34ms
memory: 2008kb

input:

5000
576963277 817862335 430151834 505200145 307373684 896252967 779450344 424741325 188693368 71249...

output:

1 3
4 5
2 4
6 8
7 9
3 7
11 12
12 13
14 15
13 14
16 17
19 20
17 19
15 17
5 16
21 22
22 23
24 25
23 25...

result:

ok Correct.

Test #12:

score: 5
Accepted
time: 17ms
memory: 2008kb

input:

5000
296887 701139 1259018 1624742 1747738 2354948 2616510 2777173 3193517 3454408 3801911 4078104 4...

output:

1 2
2 3
4 5
3 5
6 7
7 8
9 10
8 10
5 10
11 12
12 13
14 15
13 15
16 17
17 18
19 20
18 20
15 20
10 20
2...

result:

ok Correct.

Test #13:

score: 5
Accepted
time: 80ms
memory: 2024kb

input:

10000
1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 ...

output:

1 2
2 3
4 5
3 5
6 7
7 8
9 10
8 10
5 10
11 12
12 13
14 15
13 15
16 17
17 18
19 20
18 20
15 20
10 20
2...

result:

ok Correct.

Test #14:

score: 5
Accepted
time: 177ms
memory: 2068kb

input:

20000
0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 ...

output:

1 2
2 3
4 5
3 5
6 7
7 8
9 10
8 10
5 10
11 12
12 13
14 15
13 15
16 17
17 18
19 20
18 20
15 20
10 20
2...

result:

ok Correct.

Test #15:

score: 5
Accepted
time: 275ms
memory: 2104kb

input:

30000
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 0 1 1 1 ...

output:

1 2
2 3
7 8
6 7
3 6
11 12
10 11
13 14
14 15
11 14
5 12
16 17
17 18
20 21
19 21
24 25
25 26
28 29
26 ...

result:

ok Correct.

Test #16:

score: 5
Accepted
time: 297ms
memory: 2144kb

input:

40000
0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 ...

output:

2 3
4 5
3 5
6 7
7 8
5 6
11 12
12 13
13 14
16 17
15 17
6 16
21 22
22 23
24 25
23 24
26 27
29 30
26 29...

result:

ok Correct.

Test #17:

score: 0
Time Limit Exceeded

input:

50000
0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 ...

output:

2 3
3 5
8 9
9 10
11 13
10 11
4 10
14 15
17 18
14 17
20 22
23 24
21 22
15 20
7 15
26 27
30 31
26 30
3...

result:


Test #18:

score: 5
Accepted
time: 217ms
memory: 2108kb

input:

30000
23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 23333 2333...

output:

1 2
3 4
2 4
5 6
7 8
6 8
4 8
9 10
11 12
10 12
13 14
14 15
12 15
8 15
16 17
18 19
17 19
20 21
22 23
21...

result:

ok Correct.

Test #19:

score: 5
Accepted
time: 344ms
memory: 2144kb

input:

40000
45713484 162270600 502896796 450460958 129500884 513441781 557737624 340152311 679444775 35445...

output:

1 2
4 5
3 5
6 8
9 10
7 9
5 7
11 12
17 18
19 20
18 19
13 18
7 15
21 22
22 23
23 24
26 27
27 28
28 29
...

result:

ok Correct.

Test #20:

score: 0
Time Limit Exceeded

input:

50000
455891075 705915927 189674482 578895411 789714247 658466934 483470291 469989305 544838975 2828...

output:

2 3
5 7
3 5
9 10
11 12
10 11
4 10
14 15
17 18
16 18
21 22
23 24
24 25
22 24
18 23
7 21
26 27
27 28
3...

result: