oj.uz

Submission #415765

# Submission time Handle Problem Language Result Execution time Memory
415765 2021-06-01T13:29:33 Z KoD The Collection Game (BOI21_swaps) C++17
25 / 100
 138 ms 800 KB 
#include <bits/stdc++.h>
#include "swaps.h"

template <class T> using Vec = std::vector<T>;

void solve(int N, int V) {
    if (V == 5000) {
        Vec<char> done(N);
        Vec<int> ans;
        while (true) {
            Vec<int> remain;
            for (int i = 0; i < N; ++i) {
                if (!done[i]) {
                    remain.push_back(i);
                }
            }
            if (remain.empty()) {
                break;
            }
            while (remain.size() > 1) {
                Vec<int> next;
                Vec<std::array<int, 2>> ask;
                for (int i = 0; i + 1 < (int) remain.size(); i += 2) {
                    schedule(remain[i] + 1, remain[i + 1] + 1);
                    ask.push_back({remain[i + 1], remain[i]});
                }
                const auto ret = visit();
                for (int i = 0; i < (int) ret.size(); ++i) {
                    next.push_back(ask[i][ret[i]]);
                }
                if (remain.size() % 2 == 1) {
                    next.push_back(remain.back());
                }
                remain = std::move(next);
            }
            done[remain[0]] = true;
            ans.push_back(remain[0] + 1);
        }
        answer(ans);
    } else {
        Vec<std::queue<int>> cur(N);
        for (int i = 0; i < N; ++i) {
            cur[i].push(i + 1);
        }
        while (cur.size() > 1) {
            const int size = (int) cur.size() / 2;
            Vec<std::queue<int>> next(size);
            if (cur.size() % 2 == 1) {
                next.push_back(cur.back());
                cur.pop_back();
            }
            while (true) {
                Vec<int> ask;
                for (int i = 0; i < size; ++i) {
                    const int l = 2 * i;
                    const int r = 2 * i + 1;
                    if (cur[l].empty()) {
                        while (!cur[r].empty()) {
                            next[i].push(cur[r].front());
                            cur[r].pop();
                        }
                    } else if (cur[r].empty()) {
                        while (!cur[l].empty()) {
                            next[i].push(cur[l].front());
                            cur[l].pop();
                        }
                    } else {
                        schedule(cur[l].front(), cur[r].front());
                        ask.emplace_back(i);
                    }
                }
                if (ask.empty()) {
                    break;
                }
                const auto ret = visit();
                for (int i = 0; i < (int) ret.size(); ++i) {
                    const auto k = ask[i];
                    const auto idx = 2 * k + 1 - ret[i];
                    next[k].push(cur[idx].front());
                    cur[idx].pop();
                }
            }
            cur = std::move(next);
        }
        Vec<int> ans;
        while (!cur[0].empty()) {
            ans.push_back(cur[0].front());
            cur[0].pop();
        }
        answer(ans);
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 13 ms 208 KB Correct
3 Correct 46 ms 284 KB Correct
4 Correct 90 ms 300 KB Correct
5 Correct 103 ms 304 KB Correct
6 Correct 95 ms 304 KB Correct
7 Correct 75 ms 424 KB Correct
8 Correct 138 ms 316 KB Correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 9 ms 200 KB Correct
3 Correct 49 ms 296 KB Correct
4 Correct 126 ms 308 KB Correct
5 Correct 131 ms 288 KB Correct
6 Correct 103 ms 312 KB Correct
7 Correct 98 ms 308 KB Correct
8 Correct 99 ms 412 KB Correct
9 Correct 24 ms 712 KB Correct
10 Correct 10 ms 712 KB Correct
11 Correct 13 ms 712 KB Correct
12 Runtime error 25 ms 712 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 8 ms 204 KB Correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 8 ms 204 KB Correct
3 Correct 2 ms 204 KB Correct
4 Correct 17 ms 200 KB Correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 12 ms 256 KB Correct
3 Correct 29 ms 280 KB Correct
4 Correct 113 ms 304 KB Correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Correct
2 Correct 12 ms 256 KB Correct
3 Correct 29 ms 280 KB Correct
4 Correct 113 ms 304 KB Correct
5 Correct 2 ms 200 KB Correct
6 Correct 11 ms 200 KB Correct
7 Correct 42 ms 284 KB Correct
8 Correct 115 ms 304 KB Correct
9 Correct 94 ms 308 KB Correct
10 Correct 121 ms 312 KB Correct
11 Correct 117 ms 308 KB Correct
12 Correct 99 ms 312 KB Correct
13 Correct 2 ms 200 KB Correct
14 Correct 11 ms 200 KB Correct
15 Correct 36 ms 200 KB Correct
16 Correct 104 ms 316 KB Correct

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 296 KB Correct
3 Correct 28 ms 292 KB Correct
4 Correct 121 ms 304 KB Correct
5 Runtime error 10 ms 712 KB Execution killed with signal 13

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 7 ms 296 KB Correct
3 Correct 28 ms 292 KB Correct
4 Correct 121 ms 304 KB Correct
5 Runtime error 10 ms 712 KB Execution killed with signal 13

Subtask #9
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 12 ms 200 KB Correct
3 Correct 44 ms 288 KB Correct
4 Correct 107 ms 304 KB Correct
5 Runtime error 10 ms 800 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 12 ms 200 KB Correct
3 Correct 44 ms 288 KB Correct
4 Correct 107 ms 304 KB Correct
5 Runtime error 10 ms 800 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 10 ms 292 KB Correct
3 Correct 43 ms 284 KB Correct
4 Correct 120 ms 312 KB Correct
5 Runtime error 10 ms 796 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #12
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct
2 Correct 10 ms 292 KB Correct
3 Correct 43 ms 284 KB Correct
4 Correct 120 ms 312 KB Correct
5 Runtime error 10 ms 796 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -