UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214247#2022. ax_add_b603ms1324kbC++1.7kb2024-11-16 20:14:282024-11-16 23:12:10

answer

#include<bits/stdc++.h>

namespace IO
{
	template<typename Type>
	void read(Type &x){
		char ch=getchar();
		x=0;bool f=0;
		while(ch<'0'||ch>'9')
			f|=(ch=='-'),ch=getchar();
		while(ch>='0'&&ch<='9')
			x=((x<<1)+(x<<3)+(ch^48)),ch=getchar();
		x=f?-x:x;
	}
}

using namespace std;

#define N 32005
#define M 4000005

int n,maxval,pos,idx,tot,L,R,ans;
int a[N],cnt[N],seq[N];

struct sol
{
	int l,r;
}s1[M*15];

void solve(int l,int r,int val)
{
	pos=0;
	for(int i=l;i<=r;i++)
		if(a[i]==val) seq[++pos]=i;
	if(pos==1) R=seq[1];
	if(pos>1){
		tot=seq[pos/2];
		L=tot-1;
		for(int i=pos/2-1;i>=1;i--){
			for(int j=seq[i];j<L;j++){
				s1[++idx]={j,j+1};
				swap(a[j],a[j+1]);
			}
			L--;
		}L++;
		R=tot+1;
		for(int i=pos/2+1;i<=pos;i++){
			for(int j=seq[i];j>R;j--){
				s1[++idx]={j-1,j};
				swap(a[j-1],a[j]);
			}
			R++;
		}R--;
	}
	if(l<R) s1[++idx]={l,R};
	for(int i=l,j=R;i<j;i++,j--)
		swap(a[i],a[j]);
//	printf("%d\n",val);
//	for(int i=1;i<=n;i++)
//		printf("%d ",a[i]);
//	puts("");
}

int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	IO::read(n);
	for(int i=1;i<=n;i++)
		IO::read(a[i]),maxval=max(maxval,a[i]),cnt[a[i]]++;
	for(int i=1;i<=maxval;i++)
		cnt[i]+=cnt[i-1];
	for(int i=0;i<maxval;i++){
		if(cnt[i]==cnt[i-1]) continue ;
//		printf("%d %d %d\n",cnt[i-1]+1,n,i);
		solve(cnt[i-1]+1,n,i);
//		for(int i=1;i<=n;i++)
//			printf("%d ",a[i]);
//		printf("\n%d\n",idx);
	}
	printf("%d\n",idx);
//	for(int i=1;i<=idx;i++)
//		ans+=(s1[i].r-s1[i].l+1);
//	printf("%d\n",ans);
//	for(int i=1;i<=n;i++)
//		printf("%d ",a[i]);
//	puts("");
	for(int i=1;i<=idx;i++)
		printf("%d %d\n",s1[i].l,s1[i].r);
}

Details

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

Subtask #1:

score: 20
Accepted

Test #1:

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

input:

63
19732 30594 10113 7702 9784 6421 4697 13517 5317 8508 26509 15653 2986 31587 11246 12158 24378 49...

output:

59
1 43
2 31
3 37
4 33
5 32
6 50
7 55
8 18
9 22
10 44
11 42
12 61
13 45
14 31
15 57
16 45
17 27
18 5...

result:

ok ok,using 1062 times

Test #2:

score: 0
Accepted
time: 1ms
memory: 1276kb

input:

25
21264 13876 11861 12802 18452 3136 17660 21163 14140 20632 25998 22051 10612 12680 7873 23249 274...

output:

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

result:

ok ok,using 216 times

Test #3:

score: 0
Accepted
time: 0ms
memory: 1288kb

input:

95
26373 31391 7777 12225 25301 24166 2461 4926 15751 18727 29175 18511 17455 16025 16845 6723 3477 ...

output:

89
1 92
2 21
3 17
4 21
5 45
6 11
7 86
8 47
9 38
10 64
11 95
12 81
13 68
14 19
15 67
16 56
17 64
18 9...

result:

ok ok,using 2489 times

Test #4:

score: 0
Accepted
time: 0ms
memory: 1284kb

input:

100
15104 1621 22502 12704 13109 9592 1390 22280 23468 26863 23084 10981 20492 7842 12883 16636 2565...

output:

107
1 70
2 51
3 20
4 31
5 64
6 53
7 9
8 69
9 13
10 85
11 76
12 64
13 22
14 66
15 51
16 99
17 20
18 3...

result:

ok ok,using 2519 times

Test #5:

score: 0
Accepted
time: 0ms
memory: 1284kb

input:

100
13822 19801 16537 25492 24250 30303 18588 13044 8538 23642 864 10878 16671 5509 13062 15457 2577...

output:

97
1 78
2 68
3 15
4 17
5 47
6 98
7 97
8 90
9 79
10 55
11 50
12 54
13 72
14 52
15 61
16 64
17 21
18 7...

result:

ok ok,using 2718 times

Subtask #2:

score: 40
Accepted

Test #6:

score: 40
Accepted
time: 0ms
memory: 1288kb

input:

197
10471 12679 10817 27406 21095 21068 9625 5396 14548 20977 29338 17674 30961 25672 4782 22715 301...

output:

205
1 140
2 37
3 62
4 119
5 170
6 141
7 144
8 127
9 69
10 125
11 135
12 165
13 138
14 195
15 38
16 6...

result:

ok ok,using 10223 times

Test #7:

score: 0
Accepted
time: 1ms
memory: 1284kb

input:

354
28133 31628 5619 8961 1003 9779 27591 14336 31618 17755 6349 17570 25604 24107 23136 21537 16494...

output:

347
1 42
2 19
3 321
4 236
5 204
6 117
7 322
8 16
9 138
10 45
11 104
12 348
13 40
14 278
15 320
16 10...

result:

ok ok,using 31756 times

Test #8:

score: 0
Accepted
time: 0ms
memory: 1296kb

input:

512
14563 17808 18597 4341 12143 30490 13558 4331 30512 15302 14593 3642 21783 21775 23315 5766 1661...

output:

1248
1 489
2 283
3 128
4 448
5 274
6 222
7 171
8 397
9 276
10 170
11 405
12 505
13 221
14 411
15 253...

result:

ok ok,using 65574 times

Test #9:

score: 0
Accepted
time: 1ms
memory: 1324kb

input:

1000
1502 12015 26522 985 16804 3210 22284 28860 17265 9237 23503 15006 9625 30582 12808 25544 5298 ...

output:

4690
1 78
2 914
3 527
4 238
5 378
6 512
7 553
8 662
9 55
10 777
11 20
12 475
13 618
14 227
15 585
22...

result:

ok ok,using 255164 times

Test #10:

score: 0
Accepted
time: 0ms
memory: 1308kb

input:

1000
220 30195 7500 27597 28712 10097 25659 20392 16159 6016 31747 14902 5036 29017 31162 24365 2359...

output:

2632
1 816
2 941
3 176
4 441
5 893
6 372
7 185
8 881
9 384
10 852
11 655
12 732
13 244
14 26
15 625
...

result:

ok ok,using 251440 times

Subtask #3:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

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:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #16:

score: 0
Time Limit Exceeded

input:

25162
6548 134 11176 15393 24121 2053 29582 27616 22505 27930 3608 3082 22087 20841 5912 29959 21750...

output:

32766550
1 10772
2 20392
3 6712
4 6589
5 496
6 8025
7 19152
23652 23653
23651 23652
23650 23651
2364...

result: