Codeforces Round #319 (Div. 2) E. Points on Plane(分块+排序)

题意：

现在有1e6个点，（0= < x,y<=1e6），对他们进行排序，使得所有相邻两个点的曼哈顿距离之和小于2.5e9

思路：

用类似莫队那样的分块，$\sqrt{n}$进行分块，这样相邻x最多为$\sqrt(n)$，一共n个x,距离和为$n\sqrt{n}$，对于y，每个块移动n,共$\sqrt{n}$个块，所以总和还是$n\sqrt{n}$，但是需要注意一个地方，如果就是最初始的莫队，会导致总体和为$3n\sqrt{n}$，所以我们对于偶数的块上升，奇数的块下降，这样总体和就是$n\sqrt{n}$了

错误及反思：

一开始没考虑到y会出现的问题。。。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
struct poi
{int x,y,id;
}P[N];
int pos[N],n;
bool cmp(poi w,poi e)
{if(pos[w.x]==pos[e.x]){if(pos[w.x]%2==0)return w.y<e.y;else return w.y>e.y;}return w.x<e.x;
}
int main(){scanf("%d",&n);int block=(int)sqrt(1000000);for(int i=0;i<n;i++){scanf("%d%d",&P[i].x,&P[i].y);P[i].id=i+1;}for(int i=0;i<=1000000;i++)pos[i]=i/block;sort(P,P+n,cmp);for(int i=0;i<n;i++)printf("%d ",P[i].id);
}