UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214241#2022. ax_add_b0220ms32772kbC++111.4kb2024-11-16 19:30:192024-11-16 23:11:36

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;
int a[N],cnt[N],seq[N];

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

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;i<R-i+1;i++)
		swap(a[i],a[R-i+1]);
//	printf("%d\n",val);
//	for(int i=1;i<=n;i++)
//		printf("%d ",a[i]);
//	puts("");
}

int main()
{
	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=1;i<maxval;i++){
		if(cnt[i]==cnt[i-1]) continue ;
		solve(cnt[i-1]+1,n,i);
	}
	printf("%d\n",idx);
	for(int i=1;i<=idx;i++)
		printf("%d %d\n",s1[i].l,s1[i].r);
}

详细

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
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:

47
1 43
2 31
3 37
4 32
5 32
6 50
7 55
8 16
9 20
10 43
11 27
12 61
13 61
14 45
15 45
18 44
19 46
20 5...

result:

wrong answer sequence hasn't been sorted

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 1284kb

input:

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

output:

172
1 140
2 37
3 62
4 119
5 170
6 140
7 143
8 125
9 64
10 169
11 37
12 164
13 16
14 195
15 25
16 42
...

result:

wrong answer sequence hasn't been sorted

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
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 220ms
memory: 32772kb

input:

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

output:

53325
1 10772
2 20392
3 6711
4 6587
5 493
6 8024
7 19151
23652 23653
23651 23652
23650 23651
23649 2...

result:

wrong answer too many times