Proficient.
Put your skills to the test.

Problem summary

Bridge directions describe comparisons of distinct tower heights, with at most 20 corrupted directions. Every pair consecutive in the true height order has a bridge. Recover the increasing height order using a checker that reveals whether a queried supplied direction is corrupted.

Constraints

N ≤ 100000; M ≤ min(N*(N−1)/2,500000); at most 20 corrupted directions; at most 10^7 checker calls.

Worked example

An independently prepared example for this explanation.

Local mock: solve(4,{0,2,3},{2,1,1}); true order {0,2,1,3}.

Return {0,2,1,3}.

Solution analysis

1. Verify every supplied bridge exactly once. The checker returns true when its from endpoint is higher than its to endpoint, so reverse that edge if and only if the checker returns true. Every resulting edge points from lower to higher.
2. Apply Kahn’s topological sorting to the corrected directed graph. It is acyclic because height strictly increases along each edge. The guaranteed bridges between consecutive heights form a Hamiltonian increasing path, so the topological order is unique and equals the desired height order.
3. For the official example, comparisons 0→2 and 2→1 are correct, while 3→1 is reversed to 1→3. The corrected path gives 0,2,1,3. This method always uses M calls, at most 500000 and below the explicit 10^7 cap. Its competition score still depends on M relative to the official 2*N*K+1 query target; maximum score is not guaranteed.

Why it works

Checking and conditionally reversing each edge gives precisely its true lower-to-higher orientation. Any topological ordering respects all true consecutive-height edges; following those edges forces every tower into its true relative position. Kahn’s algorithm returns such an ordering, so its returned vector is exactly the required increasing order.

Watch out. check returns true for corruption, so true means reverse the supplied direction. The prose introduction mentions descending order once, but the function specification and example require increasing order. This implementation obeys that specified interface.

Grader-linked C++17 module using crption.h; no main. The example is the official function communication. All-edge verification is correct across the full input bounds and explicit call cap; its score may be below maximum when M exceeds the scoring target.

#include"crption.h"
#include<vector>
#include<queue>
// Algorithm: Verify every supplied bridge exactly once.
using namespace std;
vector<int>solve(const int&N,const vector<int>&from,const vector<int>&to){
    vector<vector<int>>graph(N);
    vector<int>indegree(N,0);
    for(int i=0;i<static_cast<int>(from.size());++i){
        int lower=from[i],higher=to[i];
        if(check(from[i],to[i])){
            lower=to[i];
            higher=from[i];
        }
        graph[lower].push_back(higher);
        ++indegree[higher];
    }
    queue<int>ready;
    for(int vertex=0;vertex<N;++vertex){
        if(indegree[vertex]==0){
            ready.push(vertex);
        }
    }
    vector<int>order;
    while(!ready.empty()){
        int vertex=ready.front();
        ready.pop();
        order.push_back(vertex);
        for(int next:graph[vertex]){
            if(--indegree[next]==0){
                ready.push(next);
            }
        }
    }
    return order;
}