Submission #740566

#	Time	Username	Problem	Language	Result	Execution time	Memory
740566		danikoynov	Mechanical Doll (IOI18_doll)	C++14	0 / 100	5 ms	9684 KiB

doll

#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 (stderr)

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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56