oj.uz

Submission #1068148

# Submission time Handle Problem Language Result Execution time Memory
1068148 2024-08-21T08:02:58 Z mc061 Mechanical Doll (IOI18_doll) C++17
53 / 100
 616 ms 46636 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);

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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 6448 KB Output is correct
3 Correct 13 ms 5212 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 25 ms 7864 KB Output is correct
7 Correct 1 ms 344 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 6448 KB Output is correct
3 Correct 13 ms 5212 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 25 ms 7864 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 75 ms 11404 KB Output is correct
9 Correct 81 ms 11496 KB Output is correct
10 Correct 104 ms 17268 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 18 ms 6448 KB Output is correct
3 Correct 13 ms 5212 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 3932 KB Output is correct
6 Correct 25 ms 7864 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 75 ms 11404 KB Output is correct
9 Correct 81 ms 11496 KB Output is correct
10 Correct 104 ms 17268 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 183 ms 23584 KB Output is correct
15 Correct 84 ms 11892 KB Output is correct
16 Correct 157 ms 18108 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 152 ms 20196 KB Output is correct
21 Correct 0 ms 348 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 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 271 ms 22392 KB Output is correct
3 Partially correct 616 ms 43596 KB Output is partially correct
4 Partially correct 610 ms 45708 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Correct 271 ms 22392 KB Output is correct
3 Partially correct 616 ms 43596 KB Output is partially correct
4 Partially correct 610 ms 45708 KB Output is partially correct
5 Partially correct 176 ms 31076 KB Output is partially correct
6 Partially correct 205 ms 34660 KB Output is partially correct
7 Partially correct 203 ms 33608 KB Output is partially correct
8 Partially correct 267 ms 36964 KB Output is partially correct
9 Partially correct 512 ms 34512 KB Output is partially correct
10 Partially correct 594 ms 46636 KB Output is partially correct
11 Partially correct 509 ms 39456 KB Output is partially correct
12 Partially correct 272 ms 26048 KB Output is partially correct
13 Partially correct 133 ms 22976 KB Output is partially correct
14 Partially correct 118 ms 21948 KB Output is partially correct
15 Partially correct 119 ms 20336 KB Output is partially correct
16 Partially correct 4 ms 860 KB Output is partially correct
17 Partially correct 216 ms 20496 KB Output is partially correct
18 Partially correct 214 ms 20668 KB Output is partially correct
19 Partially correct 207 ms 22072 KB Output is partially correct
20 Partially correct 179 ms 27832 KB Output is partially correct
21 Partially correct 390 ms 34484 KB Output is partially correct
22 Partially correct 197 ms 26556 KB Output is partially correct