UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#199278#32. Sort3Mker100265ms1420kbC++2.1kb2023-12-07 20:15:132023-12-07 20:15:15

answer

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
#define maxn 3000001
#define ll long long
int n,ans;
int a[maxn];
void rotate(int l,int r)
{
	if(l>=r) return;
	printf("%d %d\n",l,r);
	ans+=(r-l+1);
	int num=0;
	for(int i=l;i<(l+r+1)>>1;i++)
	{
		swap(a[i],a[r-num]);
		num++;
	}
	return ;
}
void inplace_sort(int l,int r,int mid)
{
	if(r<mid) return ; 
    if(l==r-1)
    {
        if(a[l]>a[r])
        {
            rotate(l,r);
        }
        return;
    }
    if(l>=r) return;
    // cout<<l<<" "<<r<<" "<<mid<<endl;
    // system("pause");
    int base=(mid+1+r)/2;
    //找到左边第一个比base大的数，并输出
    if(a[mid]<=a[base])
    {
        inplace_sort(l,base-1,mid);
    }
    else
    {
        int l1=l,r1=mid,where;
        while(l1<r1)
        {
            int mid1=(l1+r1)>>1;
            if(a[mid1]>a[base]) r1=mid1;
            else l1=mid1+1;
        }
        if(a[l1]>a[base]) where=l1;
        else where=l1+1;
        rotate(where,mid);
        rotate(mid+1,base);
        rotate(where,base);
        // for(int i=1;i<=n;i++)
        // {
        //     printf("%d ",a[i]);
        // }
        // printf("\n");
        inplace_sort(l,where-1+base-mid,where-1);
        inplace_sort(where+base-mid,r,base);
    }
    
}
void merge_sort(int l,int r)
{
    if(l==r) return;
    if(l+1==r)
    {
    	if(a[l]>a[r])
    	{
    		rotate(l,r);
		}
		return ;
	}
    int mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    inplace_sort(l,r,mid);
    return ;
}
int main()
{
//     freopen("T2.in","r",stdin);
//     freopen("T2.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    merge_sort(1,n);
    cout<<"-1 -1"<<endl;
    cout<<endl;
    // cout<<ans<<endl;
    // for(int i=1;i<=n;i++)
    // {
    // 	printf("%d ",a[i]);
	//  }
    return 0;
}
/*
10
11 4 5 1 4 1 91 9 8 10
17
52 50 50 74 61 46 84 85 73 23 94 53 97 98 65 87 29
*/
源文件, 语言: C++

详细

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

Test #1:

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

input:

5
0 0 0 1 1

output:

-1 -1

result:

ok Correct.

Test #2:

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

input:

5
716816476 646500411 807499637 544792531 128057616

output:

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

result:

ok Correct.

Test #3:

score: 5
Accepted
time: 1ms
memory: 1224kb

input:

7
0 0 1 0 0 0 0

output:

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

result:

ok Correct.

Test #4:

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

input:

7
685386610 762888212 32009424 450956771 498508039 313999604 331164353

output:

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

result:

ok Correct.

Test #5:

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

input:

10
1 1 0 0 0 0 0 1 1 1

output:

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

result:

ok Correct.

Test #6:

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

input:

10
552474873 603523889 451688250 856980678 746716186 316583031 509750159 895158422 895128023 276991286

output:

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

result:

ok Correct.

Test #7:

score: 5
Accepted
time: 4ms
memory: 1236kb

input:

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

output:

1 2
1 3
4 5
5 6
2 3
4 5
2 5
5 6
11 12
10 11
9 11
11 12
4 6
7 9
4 9
1 3
4 5
1 5
8 9
10 11
8 11
10 11
...

result:

ok Correct.

Test #8:

score: 5
Accepted
time: 2ms
memory: 1244kb

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:

2 3
3 4
5 6
6 7
7 8
5 6
4 6
6 7
13 14
7 8
9 12
7 12
11 12
11 13
19 20
23 24
21 22
20 22
22 23
27 28
...

result:

ok Correct.

Test #9:

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

input:

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

output:

1 2
1 2
1 3
7 8
6 7
2 4
5 6
2 6
6 7
11 12
10 11
11 12
13 14
15 16
14 15
11 12
13 14
11 14
14 15
6 8
...

result:

ok Correct.

Test #10:

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

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
3 4
4 5
9 10
8 9
6 8
5 8
14 15
15 16
16 17
8 10
11 15
8 15
13 15
13 16
21 22
24 25
22 23
22 24
2...

result:

ok Correct.

Test #11:

score: 5
Accepted
time: 6ms
memory: 1240kb

input:

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

output:

1 2
1 3
4 5
1 3
1 4
3 4
3 5
6 7
6 7
6 8
6 8
6 9
8 9
8 10
6 8
5 8
2 4
5 6
2 6
1 2
8 9
11 12
14 15
16 ...

result:

ok Correct.

Test #12:

score: 5
Accepted
time: 2ms
memory: 1240kb

input:

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

output:

2501 2502
2501 2502
2501 2503
2504 2505
2501 2503
2501 2504
2502 2504
2502 2505
2506 2507
2506 2507
...

result:

ok Correct.

Test #13:

score: 5
Accepted
time: 4ms
memory: 1264kb

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
1 3
4 5
2 3
2 4
6 7
7 8
8 9
9 10
3 5
6 8
3 8
6 8
6 9
11 12
12 13
13 14
14 15
16 18
15 18
18 19
1...

result:

ok Correct.

Test #14:

score: 5
Accepted
time: 6ms
memory: 1300kb

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:

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

result:

ok Correct.

Test #15:

score: 5
Accepted
time: 12ms
memory: 1344kb

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 4
5 6
3 6
11 12
10 11
13 14
14 15
11 12
13 14
11 14
5 8
9 12
5 12
20 21
19 21
24 2...

result:

ok Correct.

Test #16:

score: 5
Accepted
time: 13ms
memory: 1384kb

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
3 4
4 5
6 7
5 6
15 16
16 17
6 10
11 15
6 15
11 15
11 16
24 25
29 30
26 28
26 29
25 26
31 32
31 3...

result:

ok Correct.

Test #17:

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

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 4
3 5
8 9
9 10
11 12
11 13
10 11
4 7
8 10
4 10
17 18
14 16
14 17
20 21
20 22
15 19
15 20
7 13
...

result:

ok Correct.

Test #18:

score: 5
Accepted
time: 38ms
memory: 1336kb

input:

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

output:

10001 10002
10001 10002
10001 10003
10002 10003
10002 10004
10003 10004
10003 10005
10008 10009
1001...

result:

ok Correct.

Test #19:

score: 5
Accepted
time: 69ms
memory: 1376kb

input:

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

output:

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

result:

ok Correct.

Test #20:

score: 5
Accepted
time: 92ms
memory: 1416kb

input:

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

output:

1 2
1 3
3 4
5 6
5 6
5 7
5 6
4 6
3 4
8 9
8 10
11 12
12 13
8 10
8 11
3 7
8 10
3 10
3 4
2 4
1 2
7 10
7 ...

result:

ok Correct.

中文 English

Server time: 2025-01-19 10:16:29 | 开源项目