UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185195#2022. asnow_trace100261ms3392kbC++111.8kb2023-09-24 11:27:442023-09-24 12:03:56

answer

#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005],b[200005];
vector<pair<int,int> >q;
void merge_sort(int l,int r){
	//cout << l << " " << r << endl;
	if(l >= r)return;
	if(l+1 == r){
		if(b[l+1] == 0 and b[l] == 1)swap(a[l],a[r]),swap(b[l],b[r]),q.push_back({l,l+1});
		return;
	}int mid = l+r>>1;
	merge_sort(l,mid),merge_sort(mid+1,r);
	int pos1,pos3 = r+1;
	//cout << l << "  " << r << endl;
//	for(int i = l;i<=mid;i++)cout << b[i] << " ";cout << endl;
//	for(int i = mid+1;i<=r;i++)cout << b[i] << " ";cout << endl;
	if(b[mid] == 0 or b[mid+1] == 1)return;
	for(int i = l;i<=mid;i++){
		if(b[i] == 1){
			pos1 = i;break;
		}
	}for(int i = mid+1;i<=r;i++){
		if(b[i] == 1){
			pos3 = i;break;
		}
	}pos3--;
	q.push_back({pos1,pos3});
//	cout << pos1 <<"  " << pos3 << endl;
	reverse(a+pos1,a+pos3+1),reverse(b+pos1,b+pos3+1);
}
void solve(int l,int r,int d){
	if(d == -1)return;
	if(l>=r)return;
//	cout << l <<" " << r << endl;
	for(int i = l;i<=r;i++)b[i] = a[i]>>d&1;
	merge_sort(l,r);
//	for(int i = l;i<=r;i++)cout << b[i] <<" ";cout << endl;
	int pos =r+1;
	for(int i = l;i<=r;i++){
		if(b[i] == 1){
			pos = i;break;
		}
	}solve(l,pos-1,d-1),solve(pos,r,d-1);
}
signed main(){
	int mx =0;srand(time(0));
	cin >> n;
	for(int i = 1;i<=n;i++)cin >> a[i];
	//n = 32000;
	//for(int i = 1;i<=n;i++)a[i] = rand()%32000;
	for(int i = 1;i<=n;i++)mx = max(mx,a[i]);
	int pro = 1,cnt =-1;
	while(pro<=mx)pro*=2,cnt++;pro/=2;
	solve(1,n,cnt);
	cout << q.size() << '\n';
	for(int i = 0;i<q.size();i++)cout << q[i].first <<" " << q[i].second << '\n';
	int sum = 0;
	for(int i =0;i<q.size();i++)sum+=q[i].second-q[i].first+1;
//	cout << sum << endl;
//	for(int i = 1;i<=n;i++)cout << a[i] << " ";cout << endl;
	return 0;
}

Details

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

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1256kb

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: 1248kb

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: 0ms
memory: 1256kb

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: 1256kb

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: 0ms
memory: 1256kb

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: 1268kb

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: 1ms
memory: 1276kb

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: 0ms
memory: 1288kb

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: 0ms
memory: 1356kb

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: 1360kb

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: 13ms
memory: 1932kb

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: 9ms
memory: 1936kb

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: 11ms
memory: 1632kb

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: 11ms
memory: 1956kb

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: 5ms
memory: 1952kb

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: 40ms
memory: 3344kb

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: 20ms
memory: 2200kb

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: 49ms
memory: 2252kb

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: 50ms
memory: 3392kb

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: 51ms
memory: 3392kb

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