Proficient.
Put your skills to the test.

Problem summary

Each of N hidden K-dimensional points has one coordinate in each dimension; the coordinates in every dimension are a permutation of 0…N−1. Comparing two point indices reveals their relative order in every dimension simultaneously. Recover all coordinates. The task scores solutions by their number of comparisons.

Constraints

N=10,000; 2≤K≤5; dimension permutations are independent and uniformly random. There is no fixed official example.

Worked example

The official statement has no fixed sample coordinates or expected output. The test suite supplies independently generated complete permutations.

Solution analysis

1. Sort the point indices separately in each dimension. A coordinate is the point’s rank in that dimension, since the coordinates are guaranteed to be precisely 0 through N−1. Use bottom-up merge sort for deterministic O(N log N) comparisons per dimension.
2. Every judge comparison returns all K bits, so cache its result for the unordered pair of point indices. Normalize a pair to smaller index first, store the K-bit mask, and invert the requested bit when the comparator asks for the reverse order. Comparisons reused by a later dimension therefore cost no additional judge calls.
3. For example, if a dimension’s sorted order is point 2, point 0, point 1, write ranks 0,1,2 into those points’ coordinate entries. This implementation recovers every coordinate exactly for the complete domain. It is a conservative scored baseline: it does not claim the target comparison counts or maximum score; caching improves reuse, while the official scoring formula determines the achieved result.

Why it works

A cached bit equals the judge’s answer for its normalized pair, and reversing a pair reverses every strict order because coordinates are distinct. The comparator therefore gives the true coordinate order. Merge sort returns the correct ordering in each dimension. Assigning consecutive ranks reconstructs the unique promised permutation values, so every returned coordinate is exact. The cache changes only the number of oracle calls, never the ordering.

Watch out. Reset the cache for every independent call. Never compare a point with itself. Return point-major coordinates. Correct recovery alone does not guarantee maximum score.

Scored judge-library baseline, not a maximum-score claim. Include pointsort.h and link the grader. The local test harness verifies every returned coordinate and reports oracle calls.

#include"pointsort.h"
#include<algorithm>
#include<cstdint>
#include<numeric>
#include<unordered_map>
#include<vector>
// Algorithm: Sort the point indices separately in each dimension.
using namespace std;
vector<vector<int>>pointSort(int n,int dimensions){
    vector<vector<int>>answer(n,vector<int>(dimensions));
    unordered_map<uint64_t,unsigned int>cache;
    auto lessIn=[&](int a,int b,int dimension){
        bool reversed=a>b;
        int first=min(a,b);
        int second=max(a,b);
        uint64_t key=static_cast<uint64_t>(first)*n+second;
        auto found=cache.find(key);
        unsigned int mask;
        if(found==cache.end()){
            vector<bool>result=compare(first,second);
            mask=0;
            for(int d=0;d<dimensions;++d){
                if(result[d]){
                    mask|=1U<<d;
                }
            }
            cache.emplace(key,mask);
        }
        else{
            mask=found->second;
        }
        return static_cast<bool>((mask>>dimension)&1U)!=reversed;
    };
    vector<int>order(n),buffer(n);
    for(int dimension=0;dimension<dimensions;++dimension){
        iota(order.begin(),order.end(),0);
        for(int width=1;width<n;width*=2){
            for(int start=0;start<n;start+=2*width){
                int middle=min(n,start+width);
                int end=min(n,start+2*width);
                int left=start;
                int right=middle;
                for(int output=start;output<end;++output){
                    if(right==end||(left<middle&&lessIn(order[left],order[right],dimension))){
                        buffer[output]=order[left++];
                    }
                    else{
                        buffer[output]=order[right++];
                    }
                }
            }
            order.swap(buffer);
        }
        for(int rank=0;rank<n;++rank){
            answer[order[rank]][dimension]=rank;
        }
    }
    return answer;
}