Submission #1355404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1355404		yogesh_sane	Treasure (IOI24_treasure)	C++20	Compilation error	0 ms	0 KiB

treasure

#include "treasure.h"
#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;
}

Compilation message (stderr)

treasure.cpp:17:19: error: ambiguating new declaration of 'std::vector<long long int> encode(std::vector<std::pair<int, int> >)'
   17 | vector<long long> encode(vector<pair<int, int>> P) {
      |                   ^~~~~~
In file included from treasure.cpp:1:
treasure.h:4:18: note: old declaration 'std::vector<int> encode(std::vector<std::pair<int, int> >)'
    4 | std::vector<int> encode(std::vector<std::pair<int, int>> P);
      |                  ^~~~~~
treasure.cpp: In function 'std::vector<std::pair<int, int> > decode(std::vector<long long int>)':
treasure.cpp:76:32: error: no matching function for call to 'min(<brace-enclosed initializer list>)'
   76 |                 int match = min({count_rem, it->second, z_it->second});
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/vector:62,
                 from treasure.h:1:
/usr/include/c++/13/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
treasure.cpp:76:32: note:   candidate expects 2 arguments, 1 provided
   76 |                 int match = min({count_rem, it->second, z_it->second});
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   template argument deduction/substitution failed:
treasure.cpp:76:32: note:   candidate expects 3 arguments, 1 provided
   76 |                 int match = min({count_rem, it->second, z_it->second});
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~