oj.uz

Submission #698418

# Submission time Handle Problem Language Result Execution time Memory
698418 2023-02-13T12:31:32 Z Cyanmond Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 1585 ms 524288 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 13356 KB Output is correct
2 Correct 1548 ms 10668 KB Output is correct
3 Correct 1523 ms 11452 KB Output is correct
4 Correct 1468 ms 9256 KB Output is correct
5 Correct 1578 ms 10348 KB Output is correct
6 Correct 1477 ms 10008 KB Output is correct
7 Correct 1565 ms 10500 KB Output is correct
8 Correct 1456 ms 9932 KB Output is correct
9 Correct 1445 ms 9640 KB Output is correct
10 Correct 1478 ms 9836 KB Output is correct
11 Correct 1489 ms 9896 KB Output is correct
12 Correct 1455 ms 8804 KB Output is correct
13 Correct 1483 ms 9388 KB Output is correct
14 Correct 1513 ms 10012 KB Output is correct
15 Correct 1547 ms 9676 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1506 ms 8788 KB Output is correct
18 Correct 1457 ms 8868 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 878 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 846 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 13356 KB Output is correct
2 Correct 1548 ms 10668 KB Output is correct
3 Correct 1523 ms 11452 KB Output is correct
4 Correct 1468 ms 9256 KB Output is correct
5 Correct 1578 ms 10348 KB Output is correct
6 Correct 1477 ms 10008 KB Output is correct
7 Correct 1565 ms 10500 KB Output is correct
8 Correct 1456 ms 9932 KB Output is correct
9 Correct 1445 ms 9640 KB Output is correct
10 Correct 1478 ms 9836 KB Output is correct
11 Correct 1489 ms 9896 KB Output is correct
12 Correct 1455 ms 8804 KB Output is correct
13 Correct 1483 ms 9388 KB Output is correct
14 Correct 1513 ms 10012 KB Output is correct
15 Correct 1547 ms 9676 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1506 ms 8788 KB Output is correct
18 Correct 1457 ms 8868 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Runtime error 878 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -