제출 #1181615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181615		sqrtxsunlight	Floppy (RMI20_floppy)	C++17	100 / 100	62 ms	12224 KiB

floppy

#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;

namespace p1
{
    vector <int> arr;
    vector <vector <int>> st;

    int n;

    void build_st ()
    {
        st.push_back (vector <int> (n, 0));
        for (int i = 0; i < n; i ++)
            st[0][i] = i;

        for (int j = 1; (1 << j) <= n; j ++)
        {
            st.push_back (vector <int> (n, 0));
            for (int i = 0; i < n; i ++)
            {
                st[j][i] = st[j - 1][i];

                if (i + (1 << j - 1) < n and arr[st[j - 1][i + (1 << j - 1)]] > arr[st[j][i]])
                    st[j][i] = st[j - 1][i + (1 << j - 1)];
            }
        }

        /*
        for (auto i: st)
        {
            for (auto j: i) cout << j << ' ';
            cout << '\n';
        }
        */
    }

    int rmq (int l, int r)
    {
        int lg = 0;
        while ((1 << lg) + l <= r + 1) lg ++;
        lg --;

        int cx = st[lg][l], cy = st[lg][r - (1 << lg) + 1];
        if (arr[cx] > arr[cy]) return cx;
        else return cy;
    }

    string ans;

    void dfs_range (int l, int r)
    {
        if (l > r) return;
        int pos = rmq (l, r);

        //cout << l << ' ' << r << ' ' << pos << endl;

        int lc = true, rc = true;
        if (pos == l) lc = false;
        if (pos == r) rc = false;

        ans += char (lc + '0');
        ans += char (rc + '0');

        dfs_range (l, pos - 1);
        dfs_range (pos + 1, r);

        return;
    }

    void solve (vector <int> v)
    {
        arr = v;
        n = arr.size ();

        build_st ();
        dfs_range (0, n - 1);

        save_to_floppy (ans);

        return;
    }
}

namespace p2 {
    struct Node {
        Node* left;
        Node* right;
        int inIdx;
        Node(): left(nullptr), right(nullptr), inIdx(-1) {}
    };

    int decodePos = 0;

    Node* decodeTree(const string &bits) {
        int hasLeft = bits[decodePos] - '0';
        int hasRight = bits[decodePos + 1] - '0';
        decodePos += 2;
        Node* node = new Node();
        if (hasLeft)
            node->left = decodeTree(bits);
        if (hasRight)
            node->right = decodeTree(bits);
        return node;
    }

    void inorderTraversal(Node* node, vector<Node*> &inorderNodes) {
        if (!node) return;
        inorderTraversal(node->left, inorderNodes);
        node->inIdx = inorderNodes.size();
        inorderNodes.push_back(node);
        inorderTraversal(node->right, inorderNodes);
    }

    void eulerTour(Node* node, int depth, vector<Node*> &euler, vector<int> &eulerDepth, vector<int> &firstOccurrence) {
        if (!node) return;
        if (firstOccurrence[node->inIdx] == -1)
            firstOccurrence[node->inIdx] = euler.size();
        euler.push_back(node);
        eulerDepth.push_back(depth);
        if (node->left) {
            eulerTour(node->left, depth + 1, euler, eulerDepth, firstOccurrence);
            euler.push_back(node);
            eulerDepth.push_back(depth);
        }
        if (node->right) {
            eulerTour(node->right, depth + 1, euler, eulerDepth, firstOccurrence);
            euler.push_back(node);
            eulerDepth.push_back(depth);
        }
    }

    vector<vector<int>> buildSparseTable(const vector<int> &eulerDepth) {
        int m = eulerDepth.size();
        int K = floor(log2(m)) + 1;
        vector<vector<int>> st(K, vector<int>(m));
        for (int i = 0; i < m; i++) {
            st[0][i] = i;
        }
        for (int k = 1; (1 << k) <= m; k++) {
            for (int i = 0; i + (1 << k) - 1 < m; i++) {
                int idx1 = st[k - 1][i];
                int idx2 = st[k - 1][i + (1 << (k - 1))];
                st[k][i] = (eulerDepth[idx1] < eulerDepth[idx2]) ? idx1 : idx2;
            }
        }
        return st;
    }

    int querySparseTable(const vector<int> &eulerDepth, const vector<vector<int>> &st, int L, int R) {
        int len = R - L + 1;
        int k = floor(log2(len));
        int idx1 = st[k][L];
        int idx2 = st[k][R - (1 << k) + 1];
        return (eulerDepth[idx1] < eulerDepth[idx2]) ? idx1 : idx2;
    }

    vector<int> solve(int N, string bits, vector<int> a, vector<int> b) {
        decodePos = 0;
        Node* root = decodeTree(bits);
        vector<Node*> inorderNodes;
        inorderTraversal(root, inorderNodes);
        vector<Node*> euler;
        vector<int> eulerDepth;
        vector<int> firstOccurrence(N, -1);
        eulerTour(root, 0, euler, eulerDepth, firstOccurrence);
        vector<vector<int>> st = buildSparseTable(eulerDepth);
        int Q = a.size();
        vector<int> ans(Q, 0);
        for (int i = 0; i < Q; i++) {
            int idxA = a[i];
            int idxB = b[i];
            if (idxA > idxB) swap(idxA, idxB);
            int firstA = firstOccurrence[idxA];
            int firstB = firstOccurrence[idxB];
            if (firstA > firstB) swap(firstA, firstB);
            int pos = querySparseTable(eulerDepth, st, firstA, firstB);
            Node* lca = euler[pos];
            ans[i] = lca->inIdx;
        }
        return ans;
    }
}

void read_array(int subtask_id, const vector<int>& v)
{
    p1::solve (v);
    return;
}

vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int>& a, const vector<int>& b)
{
    return p2::solve (N, bits, a, b);
}

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