oj.uz

Submission #1068119

# Submission time Handle Problem Language Result Execution time Memory
1068119 2024-08-21T07:49:01 Z mc061 Mechanical Doll (IOI18_doll) C++17
16 / 100
 1000 ms 50116 KB 
#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

vector<int> get_leaf_order(int c_sz) {
    vector<int> order;
    map<pair<int, int>, int> state;
    set<int> vis;
    bool done = false;
    auto rec = [&] (auto&& self, int l, int r) -> void {
        if (l == r) {
            if (vis.count(l)) {
                done = true;
                return;
            }
            vis.insert(l);
            order.push_back(l);
            return;
        }
        int m = (l + r) >> 1;
        if (state[{l, r}] == 0) {
            self(self, l, m);
        }
        else {
            self(self, m+1, r);
        }
        state[{l, r}] ^= 1;
    };
    while (!done) {
        rec(rec, 0, c_sz-1);
    }
    return order;
}

void create_circuit(int M, std::vector<int> A) {
    vector<int> C(M+1);
    vector<vector<int>> graph(M+1);
    const int n = A.size();
    graph[0].push_back(A[0]);
    for (int i = 0; i < n-1; ++i) {
        graph[A[i]].push_back(A[i+1]);
    }
    graph[A[n-1]].push_back(0);
    int nxt_free = -1;
    map<int, pair<int, int>> sw;
    for (int i = 0; i <= M; ++i) {
        vector<int>& conns = graph[i];
        if (!conns.size()) {
            C[i] = 0;
            continue;
        }
        if (conns.size() == 1) {
            C[i] = conns.front();
            continue;
        }
        reverse(conns.begin(), conns.end());
        int lg = __lg(conns.size());
        int y = 1 << lg;
        if (y < conns.size()) {
            y <<= 1;
            while (conns.size() < y) conns.push_back(nxt_free);
        }
        reverse(conns.begin(), conns.end());
        C[i] = nxt_free--;
        vector<int> leaves;
        map<int, pair<int, int>> cur_tree;
        auto create_switches = [&] (auto&& self, int cur, int l, int r) {
            int le = r - l + 1;
            if (le == 1) {
                leaves.push_back(cur);
                return;
            }
            if (le == 2) {
                leaves.push_back(cur);
                return;
            }
            int m = (r + l) >> 1;
            cur_tree[cur].first = {nxt_free};
            sw[cur].first = cur_tree[cur].first;
            self(self, nxt_free--, l, m);
            cur_tree[cur].second = {nxt_free};
            sw[cur].second = cur_tree[cur].second;
            self(self, nxt_free--, m+1, r);
        };
        create_switches(create_switches, nxt_free+1, 0, conns.size()-1);
        vector<int> order = get_leaf_order(conns.size());
        for (int i = 0; i < order.size(); ++i) {
            int edge = conns[i];
            int leaf = order[i]/2;
            int sec = order[i]%2;
            if (sec) {
                sw[leaves[leaf]].second = edge;
            }
            else {
                sw[leaves[leaf]].first = edge;
            }
        }
    }
    vector<int> X, Y;
    for (int i = -1; i > nxt_free; --i) {
        X.push_back(sw[i].first);
        Y.push_back(sw[i].second);
    }
    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         if (y < conns.size()) {
      |             ~~^~~~~~~~~~~~~~
doll.cpp:63:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |             while (conns.size() < y) conns.push_back(nxt_free);
      |                    ~~~~~~~~~~~~~^~~
doll.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < order.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 20 ms 6748 KB Output is correct
3 Correct 14 ms 5768 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 23 ms 8540 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 20 ms 6748 KB Output is correct
3 Correct 14 ms 5768 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 23 ms 8540 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 64 ms 12240 KB Output is correct
9 Correct 53 ms 12416 KB Output is correct
10 Correct 109 ms 18836 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 440 KB Output is correct
13 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 20 ms 6748 KB Output is correct
3 Correct 14 ms 5768 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 6 ms 3932 KB Output is correct
6 Correct 23 ms 8540 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 64 ms 12240 KB Output is correct
9 Correct 53 ms 12416 KB Output is correct
10 Correct 109 ms 18836 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 440 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 141 ms 24888 KB Output is correct
15 Correct 63 ms 12920 KB Output is correct
16 Correct 100 ms 19648 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 105 ms 21716 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 525 ms 27364 KB Output is correct
3 Execution timed out 1022 ms 50116 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 525 ms 27364 KB Output is correct
3 Execution timed out 1022 ms 50116 KB Time limit exceeded
4 Halted 0 ms 0 KB -