oj.uz

Submission #553424

# Submission time Handle Problem Language Result Execution time Memory
553424 2022-04-25T19:35:51 Z timreizin Mechanical Doll (IOI18_doll) C++17
100 / 100
 126 ms 10960 KB 
#include "doll.h"
#include <array>
#include <cmath>

using namespace std;

void create_circuit(int m, std::vector<int> a)
{
    vector<int> c(m + 1, -1);
    c[0] = a.front();
    a.erase(a.begin());
    a.push_back(0);
    int n = a.size(), p = 1;
    while (p < n) p *= 2;
    if (p == 1) ++p;
    int delta = p - n, ind = 0;
    vector<array<int, 2>> adj{{0, 0}};
    auto dfs = [&delta, &adj, &ind](auto self, int h) -> int
    {
        if (h == -1) return 0;
        ++ind;
        int v = ind;
        adj.push_back({0, 0});
        if (delta & (1 << h))
        {
            delta ^= 1 << h;
            adj[v][0] = -1;
        }
        else adj[v][0] = -self(self, h - 1);
        adj[v][1] = -self(self, h - 1);
        return v;
    };
    dfs(dfs, round(log2(p)) - 1);
    vector<bool> state(adj.size());
    for (int i : a)
    {
        auto dfs = [i, &adj, &state](auto self, int v) -> void
        {
            state[v] = !state[v];
            if (adj[v][!state[v]] == 0)
            {
                adj[v][!state[v]] = i;
                return;
            }
            self(self, -adj[v][!state[v]]);
        };
        dfs(dfs, 1);
    }
    vector<int> x((int)adj.size() - 1), y((int)adj.size() - 1);
    for (int i = 1; i < adj.size(); ++i)
    {
        x[i - 1] = adj[i][0];
        y[i - 1] = adj[i][1];
    }
    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 1; i < adj.size(); ++i)
      |                     ~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 4052 KB Output is correct
3 Correct 41 ms 3628 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 65 ms 5440 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 4052 KB Output is correct
3 Correct 41 ms 3628 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 65 ms 5440 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 88 ms 7148 KB Output is correct
9 Correct 96 ms 7596 KB Output is correct
10 Correct 123 ms 10960 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 44 ms 4052 KB Output is correct
3 Correct 41 ms 3628 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 65 ms 5440 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 88 ms 7148 KB Output is correct
9 Correct 96 ms 7596 KB Output is correct
10 Correct 123 ms 10960 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 120 ms 10588 KB Output is correct
15 Correct 77 ms 6852 KB Output is correct
16 Correct 120 ms 10336 KB Output is correct
17 Correct 1 ms 292 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 123 ms 10768 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 81 ms 5444 KB Output is correct
3 Correct 73 ms 5508 KB Output is correct
4 Correct 121 ms 8248 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 81 ms 5444 KB Output is correct
3 Correct 73 ms 5508 KB Output is correct
4 Correct 121 ms 8248 KB Output is correct
5 Correct 118 ms 8844 KB Output is correct
6 Correct 122 ms 8712 KB Output is correct
7 Correct 125 ms 8836 KB Output is correct
8 Correct 125 ms 8520 KB Output is correct
9 Correct 75 ms 5516 KB Output is correct
10 Correct 117 ms 8480 KB Output is correct
11 Correct 120 ms 8208 KB Output is correct
12 Correct 85 ms 5436 KB Output is correct
13 Correct 78 ms 5812 KB Output is correct
14 Correct 86 ms 5884 KB Output is correct
15 Correct 80 ms 6068 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 80 ms 5440 KB Output is correct
18 Correct 78 ms 5444 KB Output is correct
19 Correct 83 ms 5632 KB Output is correct
20 Correct 126 ms 8448 KB Output is correct
21 Correct 120 ms 8444 KB Output is correct
22 Correct 108 ms 8416 KB Output is correct