比赛 20120418s 评测结果 C
题目名称 排序 最终得分 0
用户昵称 QhelDIV 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-04-18 11:08:16
显示代码纯文本
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("sorta.in");
ofstream fout("sorta.out");
int n,A[1000],f[1000],Pos[1000000],Ans[1000000],tot;
void Initialize()
{
int i;	
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>A[i];
		Pos[A[i]]=i;
		f[i]=A[i];
	}
}

void Ad_Hoc()
{
int i,j,k;	
	sort(f+1,f+n+1);
	for(i=n;i>=1;i--)
		if(Pos[i]!=i)
		{
			if(Pos[i]!=1)
			{
				for(j=1,k=Pos[i];j<k;j++,k--)
				{
					swap(A[j],A[k]);
					swap(Pos[A[j]],Pos[A[k]]);
				}
				Ans[++tot]=Pos[i];
			}
			for(j=1,k=i;j<k;j++,k--)
				{
					swap(A[j],A[k]);
					swap(Pos[A[j]],Pos[A[k]]);
				}
			Ans[++tot]=i;
		}
	fout<<tot<<endl;
	for(i=1;i<=tot;i++)
		fout<<Ans[i]<<endl;
}

int main()
{
	Initialize();
	
	Ad_Hoc();
	
	fin.close();
	fout.close();
	return 0;
}