Submission #698418

#	Time	Username	Problem	Language	Result	Execution time	Memory
698418		Cyanmond	Abracadabra (CEOI22_abracadabra)	C++17	10 / 100	1585 ms	524288 KiB

Main

#include <bits/stdc++.h>

int main() {
    // O(N^2)
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> P(N);
    for (auto &e : P) {
        std::cin >> e;
        --e;
    }
    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);
    }

    while (Q--) {
        int t, i;
        std::cin >> t >> i;
        --i;
        if (t < states.size()) {
            std::cout << states[t][i] + 1 << std::endl;
        } else {
            std::cout << states.back()[i] + 1 << std::endl;
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (t < states.size()) {
      |             ~~^~~~~~~~~~~~~~~

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