#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
// Constants for range separation
const long long OFFSET_Y = 500000000LL;
const long long OFFSET_RANK = 1000000000LL;
struct Point {
int x, y, id;
};
vector<int> encode(vector<pair<int, int>> P) {
int N = P.size();
vector<Point> pts(N);
for (int i = 0; i < N; i++) {
pts[i] = {P[i].first, P[i].second, i};
}
// 1. Determine Y-ranks
// Sort by Y to find the rank of each point's Y-coordinate
sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
return a.y < b.y;
});
vector<int> y_rank_of_point(N);
for (int r = 0; r < N; r++) {
y_rank_of_point[pts[r].id] = r;
}
// 2. Order these ranks by X-coordinate
sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
return a.x < b.x;
});
vector<int> ranks_in_x_order(N);
for (int i = 0; i < N; i++) {
ranks_in_x_order[i] = y_rank_of_point[pts[i].id];
}
// 3. Decide if we should flip ranks to minimize "descending steps"
// Descending steps cause the 'level' multiplier to increase.
int descending_steps = 0;
for (int i = 0; i < N - 1; i++) {
if (ranks_in_x_order[i] > ranks_in_x_order[i + 1]) descending_steps++;
}
bool should_reverse = (descending_steps > N / 2);
if (should_reverse) {
for (int i = 0; i < N; i++) {
ranks_in_x_order[i] = (N - 1) - ranks_in_x_order[i];
}
}
// 4. Build the output sheets
vector<int> sheets;
// Add X values
for (int i = 0; i < N; i++) sheets.push_back(P[i].first);
// Add Y values with offset
for (int i = 0; i < N; i++) sheets.push_back(P[i].second + OFFSET_Y);
// Add Monotonized Ranks with offset
// We add (level * N) to each rank to ensure the sequence is strictly increasing
int level = 0;
if (should_reverse) level = 1; // Small flag to tell decoder we reversed
for (int i = 0; i < N; i++) {
if (i > 0 && ranks_in_x_order[i] < ranks_in_x_order[i - 1]) {
level++;
}
long long val = (long long)level * N + ranks_in_x_order[i];
sheets.push_back((int)(OFFSET_RANK + val));
}
return sheets;
}
vector<pair<int, int>> decode(vector<int> S) {
int N = S.size() / 3;
sort(S.begin(), S.end());
// Separate sorted pools
vector<int> sorted_x, sorted_y;
vector<long long> rank_pool;
for (int i = 0; i < 3 * N; i++) {
if (i < N) sorted_x.push_back(S[i]);
else if (i < 2 * N) sorted_y.push_back(S[i] - OFFSET_Y);
else rank_pool.push_back(S[i] - OFFSET_RANK);
}
// Recover raw ranks and detect reversal
vector<int> recovered_ranks;
bool was_reversed = false;
// The first level determines reversal
// If the very first rank's level is 1, it implies the 'should_reverse' flag was set
if (rank_pool[0] / N == 1) was_reversed = true;
for (long long val : rank_pool) {
recovered_ranks.push_back(val % N);
}
// Reconstruct pairs
vector<pair<int, int>> result;
for (int i = 0; i < N; i++) {
int x = sorted_x[i];
int r = recovered_ranks[i];
// If we reversed in encoder, reverse the rank logic here
int y = was_reversed ? sorted_y[N - 1 - r] : sorted_y[r];
result.push_back({x, y});
}
return result;
}
