Submission #1068148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068148		mc061	Mechanical Doll (IOI18_doll)	C++17	53 / 100	616 ms	46636 KiB

doll

#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);

int64_t y(int a, int b) {
    return 1ll*(a*1e9)+b;
}

vector<int> get_leaf_order(int c_sz) {
    vector<int> order;
    unordered_map<int64_t, 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[y(l, r)] == 0) {
            self(self, l, m);
        }
        else {
            self(self, m+1, r);
        }
        state[y(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 (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9.0000000036 / 18
• Subtask 6: 28.0000000112 / 56