1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include<bits/stdc++.h>
#define FIN freopen("./E.in","r",stdin)
using namespace std;
typedef long long ll;
const ll maxn(1e6+5);
ll T,n,k;
struct point{
ll x,y,d;
}p[maxn];
bool cmp(point p1,point p2){
return p1.d<p2.d;
}
void rot(int n, int *x, int *y, int rx, int ry) {
if (ry == 0) {
if (rx == 1) {
*x = n-1 - *x;
*y = n-1 - *y;
}
int t = *x;
*x = *y;
*y = t;
}
}
int xy2d (int n, int x, int y) {
int rx, ry, s, d=0;
for (s=n/2; s>0; s/=2) {
rx = (x & s) > 0;
ry = (y & s) > 0;
d += s * s * ((3 * rx) ^ ry);
rot(n, &x, &y, rx, ry);
}
return d;
}
void d2xy(int n, int d, int *x, int *y) {
int rx, ry, s, t=d;
*x = *y = 0;
for (s=1; s<n; s*=2) {
rx = 1 & (t/2);
ry = 1 & (t ^ rx);
rot(s, x, y, rx, ry);
*x += s * rx;
*y += s * ry;
t /= 4;
}
}
int main(){
#ifndef ONLINE_JUDGE
FIN;
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
ll tmp_x,tmp_y;
for(ll i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
tmp_y=p[i].x-1;
tmp_x=p[i].y-1;
p[i].x=tmp_x;
p[i].y=tmp_y;
p[i].d=xy2d(pow(2,k),p[i].x,p[i].y);
}
sort(p+1,p+n+1,cmp);
for(ll i=1;i<=n;i++){
tmp_y=p[i].x+1;
tmp_x=p[i].y+1;
cout<<tmp_x<<" "<<tmp_y<<"\n";
}
}
|
