Submission #698453

#	Time	Username	Problem	Language	Result	Execution time	Memory
698453		Cyanmond	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	3049 ms	70204 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

void naive(int N, int Q, std::vector<int> P, std::vector<std::pair<i64, int>> queries) {
    std::vector<std::vector<int>> states;
    states.push_back(P);
    while (true) {
        const auto &a = states.back();
        std::vector<int> x, y;
        std::copy(a.begin(), a.begin() + (N / 2), std::back_inserter(x));
        std::copy(a.begin() + (N / 2), a.end(), std::back_inserter(y));
        std::vector<int> nextPerm;
        int j = 0;
        for (int i = 0; i < N / 2; ++i) {
            while (j != N / 2 and y[j] < x[i]) {
                nextPerm.push_back(y[j++]);
            }
            nextPerm.push_back(x[i]);
        }
        while (j != N / 2) {
            nextPerm.push_back(y[j++]);
        } 
        if (nextPerm == a) {
            break;
        }
        states.push_back(nextPerm);
    }

    for (const auto &[t, i] : queries) {
        if (t < (int)states.size()) {
            std::cout << states[t][i] << std::endl;
        } else {
            std::cout << states.back()[i] << std::endl;
        }
    }
}

constexpr int B = 400;

struct SuperArray {
    std::vector<std::vector<int>> data;
    std::vector<int> maxVal;
    int blocks, countOp;
    
    SuperArray(std::vector<int> A) {
        data.push_back(A);
        rebuild();        
    }

    void rebuild() {
        std::vector<int> a;
        for (auto &vec : data) {
            std::copy(vec.begin(), vec.end(), std::back_inserter(a));
        }
        data.clear();
        const int n = (int)a.size();
        blocks = (n + B - 1) / B;
        data.resize(blocks);
        maxVal.assign(blocks, -1);
        for (int x = 0; x < blocks; ++x) {
            for (int i = x * B; i < std::min((x + 1) * B, n); ++i) {
                data[x].push_back(a[i]);
                maxVal[x] = std::max(maxVal[x], a[i]);
            }
        }
        countOp = 0;
    }

    void incOp() {
        ++countOp;
        if (countOp >= B) {
            rebuild();
        }
    }

    int get(int i) {
        incOp();
        int sum = 0;
        int ret = -1;
        for (const auto &vec : data) {
            if (sum + (int)vec.size() <= i) {
                sum += (int)vec.size();
            } else {
                ret = vec[i - sum];
                break;
            }
        }
        return ret;
    }

    void recalc(int x) {
        maxVal[x] = -1;
        for (const auto e : data[x]) {
            maxVal[x] = std::max(maxVal[x], e);
        }
    }

    void erase(int i) {
        incOp();
        int sum = 0;
        for (int x = 0; x < blocks; ++x) {
            auto &vec = data[x];
            if (sum + (int)vec.size() <= i) {
                sum += (int)vec.size();
            } else {
                vec.erase(vec.begin() + (i - sum));
                recalc(x);
                break;
            }
        }
    }

    int find(int l, int v) {
        incOp();
        int sum = 0;
        for (int x = 0; x < blocks; ++x) {
            if (sum + (int)data[x].size() <= l or maxVal[x] < v) {
                sum += (int)data[x].size();
            } else {
                for (int i = std::max(0, l - sum); i < (int)data[x].size(); ++i) {
                    if (data[x][i] >= v) {
                        return sum + i;
                    }
                }
            }
        }
        return sum;
    }

    void insert(int i, int v) {
        incOp();
        int sum = 0;
        for (int x = 0; x < blocks; ++x) {
            auto &vec = data[x];
            if (sum + (int)vec.size() <= i) {
                sum += (int)vec.size();
            } else {
                vec.insert(vec.begin() + (i - sum), v);
                recalc(x);
                break;
            }
        }
    }

    void debug() {
        std::vector<int> a;
        for (auto &vec : data) {
            std::copy(vec.begin(), vec.end(), std::back_inserter(a));
        }
        for (const auto e : a) {
            std::cout << e << ' ';
        }
        std::cout << std::endl;
    }
};

struct Query {
    i64 t;
    int i;
    int queryId;
};

void solve(int N, int Q, std::vector<int> P, std::vector<std::pair<i64, int>> queries) {
    std::vector<Query> qs(Q);
    for (int i = 0; i < Q; ++i) {
        qs[i] = {queries[i].first, queries[i].second, i};
    }
    std::sort(qs.begin(), qs.end(), [](auto a, auto b) {
        return a.t < b.t;
    });
    SuperArray ar(P);
    std::vector<int> answer(Q);
    auto answerQuery = [&](const int t) {
        static int i = 0;
        if (t == -1) {
            while (i != Q) {
                answer[qs[i].queryId] = ar.get(qs[i].i);
                ++i;
            }
        } else {
            while (i != Q and qs[i].t == t) {
                answer[qs[i].queryId] = ar.get(qs[i].i);
                ++i;
            }
        }
    };
    answerQuery(0);

    int countShuffle = 0, minPos = N;
    for (int v = N; v >= 1; --v) {
        if (minPos == N / 2) {
            break;
        }
        const int pos = ar.find(0, v);
        if (pos >= N / 2) {
            minPos = std::min(minPos, pos);
            continue;
        }
        const int w = minPos - N / 2;
        const int dist = N / 2 - pos;
        const int c = (dist + w - 1) / w;
        for (int gomi = 0; gomi < c; ++gomi) {
            int l = 0;
            for (int i = N / 2; i < minPos; ++i) {
                const int val = ar.get(i);
                int p = ar.find(l, val);
                if (p >= i) {
                    p = i;
                }
                ar.erase(i);
                ar.insert(p, val);
                l = p + 1;
            }
            answerQuery(++countShuffle);
            // ar.debug();
        }
        minPos = std::min(minPos, ar.find(0, v));
    }
    answerQuery(-1);

    for (const auto e : answer) {
        std::cout << e << std::endl;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // O(N^2)
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> P(N);
    for (auto &e : P) {
        std::cin >> e;
    }
    std::vector<std::pair<i64, int>> queries(Q);
    for (auto &[t, i] : queries) {
        std::cin >> t >> i;
        --i;
    }
    solve(N, Q, P, queries);
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25