oj.uz

Submission #740592

# Submission time Handle Problem Language Result Execution time Memory
740592 2023-05-12T18:23:32 Z danikoynov Mechanical Doll (IOI18_doll) C++14
37 / 100
 181 ms 20228 KB 
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;

int n, m, a[maxn];
vector < int > c, x, y;

struct state
{
    int dev, lf_child, rf_child;

    state()
    {
        dev = 0;
        lf_child = rf_child = -1;
    }
};

state tree[4 * maxn];
int build(int left, int right)
{
    if (left == right)
        return - 1;
    int node = x.size() + 1;
    x.push_back(0);
    y.push_back(0);
    int mid = (left + right) / 2;
    tree[node].lf_child = build(left, mid);
    tree[node].rf_child = build(mid + 1, right);
    x[node - 1] = - tree[node].lf_child;
    y[node - 1] = - tree[node].rf_child;

    //cout << node << " : " << tree[node].lf_child << endl;
    //cout << node << " : " << tree[node].rf_child << endl;
    tree[node].dev = node;
    return node;
}
int pos[4 * maxn];

void simulate_path(int node, int val)
{
    if (pos[node] == 0)
    {
        if (tree[node].lf_child == -1)
        {
            x[node - 1] = val;
        }
        else
        {
            simulate_path(tree[node].lf_child, val);
        }
        pos[node] = 1;
    }
    else
    {
        if (tree[node].rf_child == -1)
        {
            y[node - 1] = val;
        }
        else
        {
            simulate_path(tree[node].rf_child, val);
        }
        pos[node] = 0;
    }
}
void create_circuit(int M, vector<int> A)
{
    n = A.size();
    m = M;
    for (int i = 0; i < A.size(); i ++)
        a[i] = A[i];
     c.resize(m + 1);


    for (int i = 0; i <= m; i ++)
        c[i] = -1;

    int nec = 1;
    while(nec < n + 1)
        nec *= 2;
    ///cout << nec << endl;
    int root = build(0, nec - 1);
    for (int i = 0; i < (nec - (n + 1)); i ++)
        simulate_path(root, - root);

    for (int i = 0; i <= n; i ++)
    {
        simulate_path(root, a[i]);
    }
    /**for (int i = 0; i <= m; i ++)
    {
        create_node(i);
        continue;

    }*/
    /**for (int i = 0; i <= m; i ++)
        cout << c[i] << " ";
    cout << endl;
    for (int i = 0; i < x.size(); i ++)
        cout << x[i] << " " << y[i] << endl;*/
    answer(c, x, y);
}

Compilation message

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 9684 KB Output is partially correct
2 Partially correct 139 ms 18656 KB Output is partially correct
3 Partially correct 142 ms 18644 KB Output is partially correct
4 Partially correct 141 ms 19580 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 9684 KB Output is partially correct
2 Partially correct 139 ms 18656 KB Output is partially correct
3 Partially correct 142 ms 18644 KB Output is partially correct
4 Partially correct 141 ms 19580 KB Output is partially correct
5 Partially correct 155 ms 20228 KB Output is partially correct
6 Partially correct 150 ms 20024 KB Output is partially correct
7 Partially correct 144 ms 20044 KB Output is partially correct
8 Partially correct 146 ms 19856 KB Output is partially correct
9 Partially correct 123 ms 18644 KB Output is partially correct
10 Partially correct 150 ms 19712 KB Output is partially correct
11 Partially correct 141 ms 19468 KB Output is partially correct
12 Partially correct 139 ms 18820 KB Output is partially correct
13 Partially correct 133 ms 19156 KB Output is partially correct
14 Partially correct 136 ms 19244 KB Output is partially correct
15 Partially correct 164 ms 19372 KB Output is partially correct
16 Partially correct 7 ms 10068 KB Output is partially correct
17 Correct 70 ms 15004 KB Output is correct
18 Partially correct 151 ms 18884 KB Output is partially correct
19 Partially correct 134 ms 18784 KB Output is partially correct
20 Partially correct 181 ms 19588 KB Output is partially correct
21 Partially correct 131 ms 19440 KB Output is partially correct
22 Partially correct 176 ms 19468 KB Output is partially correct