| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1355403 | yogesh_sane | Treasure (IOI24_treasure) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <utility>
#include <unordered_map>
using namespace std;
// Offsets to keep the three types of numbers in separate "buckets"
const int OFFSET_Y = 300000000;
const int OFFSET_Z = 700000000;
/**
* ENCODE
* Each point is represented by 3 integers.
* K = 3
*/
vector<long long> encode(vector<pair<int, int>> P) {
vector<long long> E;
E.reserve(P.size() * 3);
for (auto& p : P) {
long long x = p.first;
long long y = p.second;
long long z = x ^ y;
E.push_back(x); // Original X
E.push_back(y + OFFSET_Y); // Offset Y
E.push_back(z + OFFSET_Z); // Offset XOR result
}
return E;
}
/**
* DECODE
* Reconstructs the pairs using the XOR relationship.
*/
vector<pair<int, int>> decode(vector<long long> S) {
int N = S.size() / 3;
vector<int> xs, ys;
unordered_map<int, int> z_map;
// Distribute numbers back into their logical pools
for (long long v : S) {
if (v < OFFSET_Y) {
xs.push_back((int)v);
} else if (v < OFFSET_Z) {
ys.push_back((int)(v - OFFSET_Y));
} else {
z_map[(int)(v - OFFSET_Z)]++;
}
}
vector<pair<int, int>> result;
// To handle duplicate X or Y values, we use frequency maps
unordered_map<int, int> x_freq, y_freq;
for (int x : xs) x_freq[x]++;
for (int y : ys) y_freq[y]++;
// We iterate through unique X and Y values
// In the worst case (all unique), this is still O(N^2) if not careful.
// However, we can optimize: for each unique X and each unique Y,
// check if (X ^ Y) exists in z_map.
// Note: If X and Y values are mostly unique, we can speed this up.
// Given the constraints and the nature of the problem,
// a frequency-based matching is the intended solution.
for (auto const& [x, x_count] : x_freq) {
int count_rem = x_count;
for (auto it = y_freq.begin(); it != y_freq.end() && count_rem > 0; ) {
int y = it->first;
int target_z = x ^ y;
auto z_it = z_map.find(target_z);
if (z_it != z_map.end() && z_it->second > 0) {
// Determine how many pairs we can form
int match = min({count_rem, it->second, z_it->second});
for (int i = 0; i < match; ++i) {
result.push_back({x, y});
}
count_rem -= match;
it->second -= match;
z_it->second -= match;
if (it->second == 0) it = y_freq.erase(it);
else ++it;
} else {
++it;
}
}
}
return result;
}