oj.uz

Submission #740602

# Submission time Handle Problem Language Result Execution time Memory
740602 2023-05-12T19:00:05 Z danikoynov Mechanical Doll (IOI18_doll) C++14
100 / 100
 188 ms 25292 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 qleft, qright, sum;
int build(int left, int right)
{
    if (left >= qleft && right <= qright)
    {
        sum ++;
        return -1;
    }
    if (left == right)
    {
        sum ++;
        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];
struct element
{
    int type, idx, val;

    element(int _type, int _idx, int _val)
    {
        type = _type;
        idx = _idx;
        val = _val;
    }

};
vector < element > fin;

bool cmp(element e1, element e2)
{
    if (e1.idx == e2.idx)
        return e1.type < e2.type;
    return e1.idx < e2.idx;
}
bool cmp2(element e1, element e2)
{
    return e1.val < e2.val;
}

void simulate_path(int node, int val)
{
    ///cout << "simulate " << node << " " << val << endl;
    if (pos[node] == 0)
    {
        if (tree[node].lf_child == -1)
        {
            fin.push_back(element(0, node - 1, val));
            ///x[node - 1] = val;
        }
        else
        {
            simulate_path(tree[node].lf_child, val);
        }
        pos[node] = 1;
    }
    else
    {
        if (tree[node].rf_child == -1)
        {
                      fin.push_back(element(1, node - 1, val));
            ///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;

    qleft = 0;
    qright = (nec - (n  + 1)) - 1;

    int root = build(0, nec - 1);

    for (int i = 0; i < nec; i ++)
        simulate_path(root, i);

    sort(fin.begin(), fin.end(), cmp);
    reverse(fin.begin(), fin.end());
    int rub = nec - (n + 1);

    for (int k = 0; k < rub; k ++)
    {
        element el = fin.back();
        fin.pop_back();
        ///cout << el.idx << " :: " << el.type << endl;

        if (el.type == 0)
            x[el.idx] = - root;
        else
            y[el.idx] =  - root;
    }
    ///cout << sum << " " << fin.size() << endl;
    sort(fin.begin(), fin.end(), cmp2);
    for (int k = 0; k < n + 1; k ++)
    {
        element el = fin[k];
        if (el.type == 0)
            x[el.idx] = a[k];///, cout << "left " << el.idx << " " << a[k] << endl;
        else
            y[el.idx] = a[k];///, cout << "right " << el.idx << " " << a[k] << endl;
    }
    /**for (int i = 0; i <= m; i ++)
    {
        create_node(i);
        continue;

    }*/
    /**cout << "--------------" << endl;
    for (int i = 0; i <= m; i ++)
        cout << c[i] << " ";
    cout << endl;
    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:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < A.size(); i ++)
      |                     ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 62 ms 16332 KB Output is correct
3 Correct 60 ms 15824 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 15 ms 10836 KB Output is correct
6 Correct 85 ms 18120 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 62 ms 16332 KB Output is correct
3 Correct 60 ms 15824 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 15 ms 10836 KB Output is correct
6 Correct 85 ms 18120 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 127 ms 20964 KB Output is correct
9 Correct 117 ms 21468 KB Output is correct
10 Correct 188 ms 25292 KB Output is correct
11 Correct 6 ms 9712 KB Output is correct
12 Correct 5 ms 9668 KB Output is correct
13 Correct 5 ms 9708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 62 ms 16332 KB Output is correct
3 Correct 60 ms 15824 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 15 ms 10836 KB Output is correct
6 Correct 85 ms 18120 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 127 ms 20964 KB Output is correct
9 Correct 117 ms 21468 KB Output is correct
10 Correct 188 ms 25292 KB Output is correct
11 Correct 6 ms 9712 KB Output is correct
12 Correct 5 ms 9668 KB Output is correct
13 Correct 5 ms 9708 KB Output is correct
14 Correct 177 ms 24860 KB Output is correct
15 Correct 116 ms 20440 KB Output is correct
16 Correct 173 ms 24688 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 5 ms 9712 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 163 ms 25140 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 5 ms 9704 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9624 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 5 ms 9708 KB Output is correct
6 Correct 5 ms 9704 KB Output is correct
7 Correct 5 ms 9708 KB Output is correct
8 Correct 5 ms 9648 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 111 ms 18636 KB Output is correct
3 Correct 103 ms 18516 KB Output is correct
4 Correct 153 ms 21684 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 111 ms 18636 KB Output is correct
3 Correct 103 ms 18516 KB Output is correct
4 Correct 153 ms 21684 KB Output is correct
5 Correct 161 ms 23120 KB Output is correct
6 Correct 158 ms 22740 KB Output is correct
7 Correct 157 ms 22864 KB Output is correct
8 Correct 156 ms 22432 KB Output is correct
9 Correct 112 ms 18576 KB Output is correct
10 Correct 157 ms 22348 KB Output is correct
11 Correct 156 ms 21988 KB Output is correct
12 Correct 107 ms 18832 KB Output is correct
13 Correct 118 ms 19216 KB Output is correct
14 Correct 106 ms 19344 KB Output is correct
15 Correct 109 ms 19444 KB Output is correct
16 Correct 7 ms 9940 KB Output is correct
17 Correct 95 ms 17328 KB Output is correct
18 Correct 103 ms 18768 KB Output is correct
19 Correct 106 ms 18832 KB Output is correct
20 Correct 150 ms 22344 KB Output is correct
21 Correct 148 ms 22036 KB Output is correct
22 Correct 151 ms 22088 KB Output is correct