Proficient.
Put your skills to the test.

Problem summary

Recover a hidden permutation using compare(x,y), which tests p[x]<p[y], and free divisible(x,y,d), which tests whether d divides |p[x]−p[y]|. Full comparison-score requires at most⌊N/2⌋ compare calls.

Source clarification. This is a grader/oracle task, not ordinary stdin/stdout. The full-score divide-and-conquer comparison bound follows the official editorial: https://infos.infosbg.com/files/Contests/ETI/2022/B/analyses/B6_sorting_analysis.pdf

Constraints

1≤N≤500000; the hidden values are a permutation of1..N. Oracle positions and divisors must lie in1..N.

Worked example

Original statement sample.

3
2 3 1

2 3 1

Solution analysis

1. Partition positions into equal-residue classes modulo2, then4,8,… . Within a group whose hidden values form an arithmetic progression of step s, a divisible query with2s separates the alternating values into two groups. Recursively sort each group by its hidden values.
2. Merge the two sorted groups by alternating their positions. If their sizes differ, the larger group contains the smaller first value. If both sizes are at least2 and equal, let the parent size be t. The difference between the smaller first value and the other group’s last value is(t−1)s; in the reverse orientation it is(t−3)s. Since s is a power of two and t−1 is odd, one divisible query with divisor t−1 distinguishes them.
3. Only a group of size2 needs a paid compare call; these pairs are disjoint, so at most⌊N/2⌋ such calls occur. Once all positions are sorted, assign values1,2,…,N to them. For hidden[2,3,1], modulo2 groups contain positions[2,3] and[1]; the larger group starts first, yielding sorted positions[3,1,2], and therefore the recovered array[2,3,1].

Why it works

Each residue-class group consists of consecutive terms of an arithmetic progression. Splitting modulo twice its step separates its alternating terms. The size and divisibility rules identify which child begins with the smaller term, so alternating their recursively sorted orders gives the exact parent order. Induction sorts the full set of positions. Only disjoint two-element groups use compare, establishing the full-score comparison bound.

Watch out. divisible is not a remainder-valued query; it returns only a Boolean. Handle size2 directly so no divisor greater than N is requested. Return values at original positions, not merely the sorted position list. The real judge supplies sorting.h and the hidden values remain inaccessible.

Compile the local simulator with g++ -std=c++17 -DLOCAL. For the real grader, omit -DLOCAL and supply sorting.h; only solve and its helpers are submitted. The algorithm accesses hidden values exclusively through the two permitted oracles.

#include<iostream>
#include<numeric>
#include<utility>
#include<vector>
#ifndef LOCAL
#include"sorting.h"
#else
bool compare(int x,int y);
bool divisible(int x,int y,int d);
#endif
using namespace std;
vector<int>orderedPositions(vector<int>positions,int step){
    if(positions.size()<=1){
        return positions;
    }
    if(positions.size()==2){
        if(!compare(positions[0],positions[1])){
            swap(positions[0],positions[1]);
        }
        return positions;
    }
    vector<int>first;
    vector<int>second;
    int pivot=positions[0];
    for(int position:positions){
        if(position==pivot||divisible(pivot,position,2*step)){
            first.push_back(position);
        }
        else{
            second.push_back(position);
        }
    }
    first=orderedPositions(move(first),2*step);
    second=orderedPositions(move(second),2*step);
    bool firstStarts;
    if(first.size()!=second.size()){
        firstStarts=first.size()>second.size();
    }
    else{
        // Exactly one cross-endpoint difference is divisible by size-1.
        firstStarts=divisible(first.front(),second.back(),static_cast<int>(positions.size())-1);
    }
    if(!firstStarts){
        swap(first,second);
    }
    vector<int>result;
    result.reserve(positions.size());
    for(size_t i=0;i<first.size();i++){
        result.push_back(first[i]);
        if(i<second.size()){
            result.push_back(second[i]);
        }
    }
    return result;
}
vector<int>solve(int n){
    vector<int>positions(n);
    iota(positions.begin(),positions.end(),1);
    positions=orderedPositions(move(positions),1);
    vector<int>answer(n);
    for(int rank=0;rank<n;rank++){
        answer[positions[rank]-1]=rank+1;
    }
    return answer;
}
#ifdef LOCAL
vector<int>hidden;
int paidQueries=0;
bool compare(int x,int y){
    paidQueries++;
    return hidden[x]<hidden[y];
}
bool divisible(int x,int y,int d){
    int difference=hidden[x]-hidden[y];
    return difference%d==0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    hidden.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>hidden[i];
    }
    vector<int>answer=solve(n);
    for(int i=0;i<n;i++){
        if(i>0){
            cout<<' ';
        }
        cout<<answer[i];
    }
    cout<<'\n';
    if(paidQueries>n/2){
        return 1;
    }
}
#endif