#include "treasure.h"
#include <cstring>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
namespace encoder {
const int N = 40000, X = 500000001, A = 2000000001;
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], ii[N], ii_[N], pp[N];
int *vv;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (vv[ii[j]] == vv[i_])
j++;
else if (vv[ii[j]] < vv[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
vi encode(vpi xy) {
int n = xy.size();
for (int i = 0; i < n; i++)
xx[i] = xy[i].first, yy[i] = xy[i].second;
vi aa(n * 3, A - 1);
for (int i = 0; i < n; i++)
aa[i] = xx[i], aa[n + i] = X + yy[i];
for (int i = 0; i < n; i++)
ii[i] = i;
vv = yy, sort(ii, 0, n);
for (int i = 0; i < n; i++)
yy[ii[i]] = i;
vv = xx, sort(ii, 0, n);
for (int i = 0; i < n; i++) {
int p = yy[ii[i]];
ii_[pp[i] = p] = i;
}
memcpy(ii, ii_, n * sizeof *ii_);
for (int j = n - 1; j >= 0; j--) {
int i = ii[j];
aa[n * 2 + j] = X * 2 + j * (j + 1) / 2 + i;
int p = pp[i], q = pp[j];
ii[pp[i] = q] = i, ii[pp[j] = p] = j;
}
return aa;
}
}
vi encode(vpi xy) {
return encoder::encode(xy);
}
namespace decoder {
const int N = 40000, X = 500000001, A = 2000000001;
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], aa[N * 3];
int *vv;
void sort(int *aa, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, a = aa[l + rand_() % (r - l)], tmp;
while (j < k)
if (aa[j] == a)
j++;
else if (aa[j] < a) {
tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
i++, j++;
} else {
k--;
tmp = aa[j], aa[j] = aa[k], aa[k] = tmp;
}
sort(aa, l, i);
l = k;
}
}
vpi decode(vi aa_) {
int n = aa_.size() / 3;
for (int i = 0; i < n * 3; i++)
aa[i] = aa_[i];
sort(aa, 0, n * 3);
for (int i = 0; i < n; i++)
xx[i] = aa[i], yy[i] = aa[n + i] - X;
for (int j = 0; j < n; j++) {
int i = aa[n * 2 + j] - X * 2 - j * (j + 1) / 2, tmp;
tmp = yy[i], yy[i] = yy[j], yy[j] = tmp;
}
vpi xy(n);
for (int i = 0; i < n; i++)
xy[i] = make_pair(xx[i], yy[i]);
return xy;
}
}
vpi decode(vi aa) {
return decoder::decode(aa);
}
