oj.uz

Submission #740566

# Submission time Handle Problem Language Result Execution time Memory
740566 2023-05-12T17:28:45 Z danikoynov Mechanical Doll (IOI18_doll) C++14
0 / 100
 5 ms 9684 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 root = build(0, n);
    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 9604 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9604 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9604 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9684 KB state 'Y'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9684 KB state 'Y'
2 Halted 0 ms 0 KB -