Submission #1068302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068302		mc061	Mechanical Doll (IOI18_doll)	C++17	65.67 / 100	332 ms	43140 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);

map<int, pair<int, int>> sw;
int64_t h(int a, int b) {
    return (1ll*a*1e9)+b;
}
vector<int> get_ord(vector<vector<pair<int, bool>>>& tree, int root) {
    vector<bool> state(root+1, false);
    vector<bool> had(root+1, false);
    bool done = false;
    vector<int> ret;
    auto dfs = [&] (auto&& self, int v, bool fake) -> void {
        if (!tree[v].size()) {
            if (fake) return;
            if (had[v]) {
                done = true;
                return;
            }
            had[v] = true;
            ret.push_back(v);
            return;
        }
        if (!state[v]) {
            self(self, tree[v][0].first, tree[v][0].second);
        }
        else {
            self(self, tree[v][1].first, tree[v][1].second);
        }
        state[v] = state[v] ^ 1;
    };
    while (!done) dfs(dfs, root, false);
    return ret;
}
int build_top_down(int cnt_leaves, int shift, vector<int>& conns) {
    vector<vector<pair<int, bool>>> tree(4*cnt_leaves);
    int now = 0;
    vector<pair<int, bool>> inds;//ind, fake
    for (int i = 0; i < cnt_leaves; ++i) {
        inds.push_back({now++, false});
    }
    while (inds.size() > 1) {
        vector<pair<int, bool>> nxt_inds;
        for (int i = 0; i < inds.size(); i += 2) {
            tree[now].push_back(inds[i]);
            tree[now].push_back(inds[i+1]);
            nxt_inds.push_back({now++, false});
        }
        if (nxt_inds.size() != 1 && nxt_inds.size() % 2 != 0) {
            reverse(nxt_inds.begin(), nxt_inds.end());
            nxt_inds.push_back({now++, true});
            reverse(nxt_inds.begin(), nxt_inds.end());
        }
        inds.swap(nxt_inds);
    }
    int root = inds[0].first;
    vector<int> ret = get_ord(tree, root);
    vector<int> place(cnt_leaves);
    for (int i = 0; i < cnt_leaves; ++i) {
        place[ret[i]] = i;
    }
    shift += cnt_leaves;
    auto get = [&] (int ind) -> int {
        return shift+(-ind);
    };
    for (int i = 0; i < cnt_leaves; ++i) {
        if (conns[i] < 0) conns[i] = get(root);
    }
    auto fill_sw = [&] (auto&& self, int v, bool fake) -> void {
        if (fake) {
            sw[get(v)].first = get(root);
            sw[get(v)].second = get(root);
            return;
        }
        if (tree[v].front().first < cnt_leaves) {
            sw[shift+(-v)].first = conns[place[tree[v].front().first]];
            sw[shift+(-v)].second = conns[place[tree[v].back().first]];
            return;
        }
        sw[get(v)].first = get(tree[v].front().first);
        sw[get(v)].second = get(tree[v].back().first);
        self(self, tree[v].front().first, tree[v].front().second);
        self(self, tree[v].back().first, tree[v].back().second);
    };
    fill_sw(fill_sw, root, false);
    return get(root);
}


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;
    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());
        if (conns.size() % 2 != 0) conns.push_back(nxt_free);
        reverse(conns.begin(), conns.end());
        int root = build_top_down(conns.size(), nxt_free, conns);
        C[i] = root;
        nxt_free = root - 1;
    }
    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 'int build_top_down(int, int, std::vector<int>&)':
doll.cpp:47:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         for (int i = 0; i < inds.size(); i += 2) {
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 14.7580402392 / 18
• Subtask 6: 34.914797876 / 56