oj.uz

Submission #410045

# Submission time Handle Problem Language Result Execution time Memory
410045 2021-05-21T22:03:41 Z ruadhan Mechanical Doll (IOI18_doll) C++17
53 / 100
 321 ms 15868 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define sz(x) (int)x.size()

// void answer(vector<int> &C, vector<int> tmp1, vector<int> tmp2)
// {
//     for (auto &x : C)
//         cout << x << " ";
//     cout << '\n';
//     for (auto x : tmp1)
//         cout << x << " ";
//     cout << '\n';
//     for (auto x : tmp2)
//         cout << x << " ";
//     cout << '\n';
// }

int S;
vector<int> X, Y;
void build(int node, int mx_node)
{
    if (node == 1)
        X.resize(sz(X) + mx_node - 1, -S - node), Y.resize(sz(Y) + mx_node - 1, -S - node);
    if (node * 2 >= mx_node)
        return;
    X[S + node - 1] = -S - node * 2;
    Y[S + node - 1] = -S - node * 2 - 1;
    build(2 * node, mx_node), build(2 * node + 1, mx_node);
}

void create_circuit(int M, vector<int> A)
{
    int N = A.size();
    vector<int> C(M + 1);
    C[0] = A[0];

    vector<int> make_switches;
    set<int> seen;

    vector<int> adj[M + 1];
    adj[0].push_back(A[0]);
    for (int i = 0; i < N; i++)
    {
        if (i < N - 1)
            adj[A[i]].push_back(A[i + 1]);
        else
            adj[A[i]].push_back(0);

        if (adj[A[i]].size() == 1)
            C[A[i]] = adj[A[i]][0];
        else if (seen.find(A[i]) == seen.end())
        {
            make_switches.push_back(A[i]);
            seen.insert(A[i]);
        }
    }

    int sz_switches = make_switches.size();
    // for (auto x : make_switches)
    //     cout << x << " ";
    // cout << '\n';
    X.reserve(200005), Y.reserve(200005);
    S = 0;
    for (int i = 0; i < sz_switches; i++)
    {
        int root_trigger = make_switches[i];
        int root_switch = -S - 1;
        C[root_trigger] = root_switch;
        int K = sz(adj[root_trigger]);
        int log2;
        for (int i = 0; i < 32; i++)
            if ((1 << i) >= K)
            {
                log2 = i;
                break;
            }
        build(1, 1 << log2);

        auto leaves = adj[root_trigger];
        reverse(leaves.begin(), leaves.end());
        leaves.resize(1 << log2, root_switch);
        reverse(leaves.begin(), leaves.end());

        for (int i = 0; i < sz(leaves); i++)
        {
            // int mask = sz(leaves) - i - 1;
            int mask = i;
            int dest_node = 0;
            for (int j = 0; j < log2; j++)
                if ((mask >> j) & 1)
                    dest_node += 1 << (log2 - j - 1);
            dest_node += (1 << log2);
            int parent = (dest_node) / 2;
            if (2 * parent == dest_node)
                X[S + parent - 1] = leaves[i];
            else
                Y[S + parent - 1] = leaves[i];
            // cout << "dest_node = " << dest_node << ", parent = " << parent << '\n';
            // cout << "S = " << S << ", S + parent + 1 = " << S + parent + 1 << '\n';
        }

        S += (1 << log2) - 1;
    }
    answer(C, X, Y);
}

// int main()
// {
//     vector<int> A = {1, 2, 1, 2, 1, 2, 1};
//     int M = 2;
//     create_circuit(M, A);
//     return 0;
// }

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:78:14: warning: 'log2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         build(1, 1 << log2);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 33 ms 6348 KB Output is correct
3 Correct 30 ms 5164 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 48 ms 7620 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 33 ms 6348 KB Output is correct
3 Correct 30 ms 5164 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 48 ms 7620 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 167 ms 10548 KB Output is correct
9 Correct 142 ms 10776 KB Output is correct
10 Correct 321 ms 15868 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 33 ms 6348 KB Output is correct
3 Correct 30 ms 5164 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 16 ms 3788 KB Output is correct
6 Correct 48 ms 7620 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 167 ms 10548 KB Output is correct
9 Correct 142 ms 10776 KB Output is correct
10 Correct 321 ms 15868 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 239 ms 14408 KB Output is correct
15 Correct 112 ms 7400 KB Output is correct
16 Correct 185 ms 11260 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 211 ms 14080 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 1 ms 204 KB Output is partially correct
2 Correct 69 ms 5008 KB Output is correct
3 Partially correct 88 ms 9568 KB Output is partially correct
4 Partially correct 103 ms 9740 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 204 KB Output is partially correct
2 Correct 69 ms 5008 KB Output is correct
3 Partially correct 88 ms 9568 KB Output is partially correct
4 Partially correct 103 ms 9740 KB Output is partially correct
5 Partially correct 173 ms 15164 KB Output is partially correct
6 Partially correct 168 ms 15224 KB Output is partially correct
7 Partially correct 177 ms 15188 KB Output is partially correct
8 Partially correct 169 ms 15088 KB Output is partially correct
9 Partially correct 123 ms 8664 KB Output is partially correct
10 Partially correct 207 ms 14196 KB Output is partially correct
11 Partially correct 156 ms 14540 KB Output is partially correct
12 Partially correct 102 ms 9536 KB Output is partially correct
13 Partially correct 104 ms 10004 KB Output is partially correct
14 Partially correct 125 ms 10040 KB Output is partially correct
15 Partially correct 103 ms 10080 KB Output is partially correct
16 Partially correct 3 ms 460 KB Output is partially correct
17 Partially correct 81 ms 9088 KB Output is partially correct
18 Partially correct 87 ms 7364 KB Output is partially correct
19 Partially correct 84 ms 7904 KB Output is partially correct
20 Partially correct 127 ms 10448 KB Output is partially correct
21 Partially correct 129 ms 12364 KB Output is partially correct
22 Partially correct 108 ms 9384 KB Output is partially correct