Submission #1181633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181633		sqrtxsunlight	Floppy (RMI20_floppy)	C++17	100 / 100	70 ms	6820 KiB

floppy

#include "floppy.h" // Include the header provided by the problem statement
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <memory> // Required for unique_ptr if used, though direct arrays/vectors are fine too

// --- Global data for Interaction 1 (will be lost before Interaction 2) ---
// Not strictly necessary to be global, can be local to read_array
namespace interaction1 {
    std::vector<int> left_child;
    std::vector<int> right_child;
    std::vector<int> parent;
    std::string encoded_bits;

    // Recursive function to encode the tree structure (preorder)
    void encode_tree(int u) {
        if (u == -1) {
            encoded_bits += '0';
            return;
        }
        encoded_bits += '1';
        encode_tree(left_child[u]);
        encode_tree(right_child[u]);
    }
} // namespace interaction1

// --- Global data for Interaction 2 ---
namespace interaction2 {
    int N;
    std::vector<int> left_child;
    std::vector<int> right_child;
    std::vector<int> parent; // Parent needed for LCA precomputation
    std::vector<int> node_to_original_index;
    std::vector<int> original_index_to_node;
    std::string::const_iterator bit_iterator; // To iterate through the bits string

    // LCA related data (using binary lifting)
    const int MAX_LOG_N = 18; // ceil(log2(40000)) + a bit extra
    std::vector<std::vector<int>> up; // up[k][u] = 2^k-th ancestor of u
    std::vector<int> depth;

    int current_node_id = 0;
    int current_original_index = 0;

    // Recursive function to decode the bit string and build the tree structure
    int decode_tree(const std::string& bits) {
        if (bit_iterator == bits.end() || *bit_iterator == '0') {
            ++bit_iterator; // Consume the '0'
            return -1; // Represents a null child
        }

        ++bit_iterator; // Consume the '1'
        int node_id = current_node_id++;
        left_child[node_id] = decode_tree(bits);
        right_child[node_id] = decode_tree(bits);

        // Set parent pointers during reconstruction
        if (left_child[node_id] != -1) {
            parent[left_child[node_id]] = node_id;
        }
        if (right_child[node_id] != -1) {
            parent[right_child[node_id]] = node_id;
        }
        return node_id;
    }

    // Inorder traversal to assign original indices
    void assign_indices_inorder(int u) {
        if (u == -1) {
            return;
        }
        assign_indices_inorder(left_child[u]);
        // Assign original index during the inorder visit
        node_to_original_index[u] = current_original_index;
        original_index_to_node[current_original_index] = u;
        current_original_index++;
        assign_indices_inorder(right_child[u]);
    }

    // Depth First Search to compute depths and immediate parents for LCA
    void dfs_lca(int u, int p, int d) {
        depth[u] = d;
        up[0][u] = p; // Immediate parent (or -1 for root)
        if (left_child[u] != -1) {
            dfs_lca(left_child[u], u, d + 1);
        }
        if (right_child[u] != -1) {
            dfs_lca(right_child[u], u, d + 1);
        }
    }

    // Precompute LCA using binary lifting
    void build_lca(int root) {
        depth.assign(N, 0);
        up.assign(MAX_LOG_N, std::vector<int>(N, -1));

        dfs_lca(root, -1, 0); // Compute depth and up[0]

        for (int k = 1; k < MAX_LOG_N; ++k) {
            for (int u = 0; u < N; ++u) {
                if (up[k - 1][u] != -1) {
                    up[k][u] = up[k - 1][up[k - 1][u]];
                }
            }
        }
    }

    // Query LCA
    int get_lca(int u, int v) {
        if (depth[u] < depth[v]) {
            std::swap(u, v);
        }

        // Bring u to the same depth as v
        for (int k = MAX_LOG_N - 1; k >= 0; --k) {
            if (up[k][u] != -1 && depth[up[k][u]] >= depth[v]) {
                u = up[k][u];
            }
        }

        if (u == v) {
            return u;
        }

        // Lift u and v together
        for (int k = MAX_LOG_N - 1; k >= 0; --k) {
            if (up[k][u] != up[k][v]) {
                u = up[k][u];
                v = up[k][v];
            }
        }
        // Now up[0][u] == up[0][v] is the LCA
        return up[0][u];
    }

} // namespace interaction2

// --- Interaction 1 Implementation ---
void read_array(int subtask_id, const std::vector<int>& v) {
    int n = v.size();
    interaction1::left_child.assign(n, -1);
    interaction1::right_child.assign(n, -1);
    interaction1::parent.assign(n, -1);
    interaction1::encoded_bits = "";

    // Build Cartesian Tree using O(N) stack method
    std::stack<int> s;
    for (int i = 0; i < n; ++i) {
        int last_popped = -1;
        while (!s.empty() && v[s.top()] < v[i]) {
            last_popped = s.top();
            s.pop();
        }
        interaction1::left_child[i] = last_popped;
        if (last_popped != -1) {
            interaction1::parent[last_popped] = i;
        }
        if (!s.empty()) {
            interaction1::right_child[s.top()] = i;
            interaction1::parent[i] = s.top();
        }
        s.push(i);
    }

    // Find the root (the node with no parent)
    int root = -1;
    for (int i = 0; i < n; ++i) {
        if (interaction1::parent[i] == -1) {
            root = i;
            break;
        }
    }

    // Encode the tree structure
    interaction1::encode_tree(root);

    // Save the bits
    save_to_floppy(interaction1::encoded_bits);
}

// --- Interaction 2 Implementation ---
std::vector<int> solve_queries(int subtask_id, int N_in, const std::string& bits, const std::vector<int>& a, const std::vector<int>& b) {
    interaction2::N = N_in;
    interaction2::left_child.assign(N_in, -1);
    interaction2::right_child.assign(N_in, -1);
    interaction2::parent.assign(N_in, -1); // Important for LCA precomputation
    interaction2::node_to_original_index.assign(N_in, -1);
    interaction2::original_index_to_node.assign(N_in, -1);
    interaction2::bit_iterator = bits.begin();
    interaction2::current_node_id = 0; // Reset counters for reconstruction
    interaction2::current_original_index = 0;


    // 1. Reconstruct the tree structure from bits
    int root = interaction2::decode_tree(bits);
    // The parent array is partially filled by decode_tree, root's parent remains -1.

    // 2. Assign original indices using inorder traversal
    interaction2::assign_indices_inorder(root);

    // 3. Precompute LCA data structures
    interaction2::build_lca(root);

    // 4. Answer queries
    int M = a.size();
    std::vector<int> results(M);
    for (int i = 0; i < M; ++i) {
        int u_orig_idx = a[i];
        int v_orig_idx = b[i];

        // Handle query for single element range
        if (u_orig_idx == v_orig_idx) {
             results[i] = u_orig_idx;
             continue;
        }

        int u_node = interaction2::original_index_to_node[u_orig_idx];
        int v_node = interaction2::original_index_to_node[v_orig_idx];

        int lca_node = interaction2::get_lca(u_node, v_node);
        results[i] = interaction2::node_to_original_index[lca_node];
    }

    return results;
}

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72