比赛 防止浮躁的小练习v0.5 评测结果 AAAAAAAAWW
题目名称 罗伊德的防晒霜 最终得分 80
用户昵称 dududu 运行时间 0.377 s
代码语言 C++ 内存使用 0.73 MiB
提交时间 2016-10-15 18:34:02
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define lcy 19283746
#define KN 100010
struct Point
{
	int x,y;
	Point(){
		x=y=0;
	}
};

int N;
Point p[KN];
int merge_tmp[KN];

bool my_cmp(const Point &tmpa,const Point &tmpb)
{
	return tmpa.x<tmpb.x;
}

void init()
{
	cin>>N;
	for(int i=1,tmpx,tmpy;i<=N;i++)
	{
		scanf("%d %d",&p[i].x,&p[i].y);
	}
	sort(p+1,p+1+N,my_cmp);
}

int merge_sort(int l,int mid,int r)//对y排序 x方向上交换距离和即为最少交换次数 
{
	if(l>=r) return 0;//边界 
	int ans=merge_sort(l,l+(mid-l)/2,mid)+merge_sort(mid+1,mid+(r-mid)/2,r);//首先对[l,mid],[mid+1,r]排序
	 
	//假装我们已经把 [l,mid],[mid+1,r]排序好的样子 
	int i=l,j=mid+1,cur=l;//i为[l,mid]的指针(口胡),j同理,cur为临时数组的*... 
	while(i<=mid&&j<=r)
	{
		if(p[i].y>p[j].y) merge_tmp[cur++]=p[j++].y,ans+=mid-i+1;//需要交换 
		else merge_tmp[cur++]=p[i++].y;//不需要交换 
		
		while(ans>=lcy) ans-=lcy;//%lcy 
	}
	
	//临时数组中可能有未交换的 
	while(i<=mid) merge_tmp[cur++]=p[i++].y;
	while(j<=r) merge_tmp[cur++]=p[j++].y;
	
	for(i=l;i<=r;i++) p[i].y=merge_tmp[i];//复制数组 
	
	return ans;
}


int main()
{
	freopen("EOADtulad.in","r",stdin);
	freopen("EOADtulad.out","w",stdout);
	init();
	printf("%d",merge_sort(1,N/2,N));
	return 0;
}