oj.uz

Submission #782952

# Submission time Handle Problem Language Result Execution time Memory
782952 2023-07-14T12:25:40 Z faruk Mechanical Doll (IOI18_doll) C++17
37 / 100
 81 ms 12568 KB 
#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> X, Y, C;
struct trigger {
    int id;
    int type;

    trigger() {}
    trigger(int typ)  {
        if (typ != 0) {
            id = typ;
            type = 1;
        } else {
            X.push_back(0);
            Y.push_back(0);
            id = X.size();
            type = 0;
        }
    }

    void connect_parent(int par) {
        C[par] = -id;
    }

    void connect_X(trigger x) {
        if (x.type == 0)
            X[id - 1] = -x.id;
        else
            X[id - 1] = x.id;
    }

    void connect_Y(trigger y) {
        if (y.type == 0) 
            Y[id - 1] = -y.id;
        else
            Y[id - 1] = y.id;
    }
};

void set_idxs(int curr, int idx, int depth, int max_node, trigger node, vector<trigger> &targets) {
    if (curr * 2 >= max_node) {
        int xi = idx, yi = idx + (1 << depth);
        node.connect_X(trigger(targets[xi]));
        node.connect_Y(trigger(targets[yi]));
        return;
    }
    
    trigger xnode(0);
    trigger ynode(0);
    set_idxs(curr*2, idx, depth + 1, max_node, xnode, targets);
    set_idxs(curr*2+1, idx + (1 << depth), depth + 1, max_node, ynode, targets);
    node.connect_X(xnode);
    node.connect_Y(ynode);
}

void create_device(int node, trigger root, vector<trigger> targets) {
    int siz = 2, needed = 2;
    while (siz < targets.size())
        siz *= 2, needed += siz;
    while (targets.size() < siz)
    {
        targets.push_back(root);
        swap(targets[targets.size() - 1], targets[targets.size() - 2]);
    }
    set_idxs(1, 0, 0, siz, root, targets);
}

void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    C.resize(M+1);
    vector<trigger> targets;
    for (int i : A)
        targets.push_back(trigger(i));
    trigger zer;
    zer.type = 1, zer.id = 0;
    targets.push_back(zer);
    
    C[0] = -1;
    trigger rootdevice(0);
    for (int i = 1; i <= M; i++)
        C[i] = -rootdevice.id;
    create_device(0, rootdevice, targets);



    answer(C, X, Y);
}

Compilation message

doll.cpp: In function 'void create_device(int, trigger, std::vector<trigger>)':
doll.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<trigger>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while (siz < targets.size())
      |            ~~~~^~~~~~~~~~~~~~~~
doll.cpp:63:27: warning: comparison of integer expressions of different signedness: 'std::vector<trigger>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     while (targets.size() < siz)
      |            ~~~~~~~~~~~~~~~^~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:72:9: warning: unused variable 'N' [-Wunused-variable]
   72 |     int N = A.size();
      |         ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 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 1 ms 212 KB Output is partially correct
2 Partially correct 55 ms 10816 KB Output is partially correct
3 Partially correct 68 ms 10800 KB Output is partially correct
4 Partially correct 62 ms 11616 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Partially correct 55 ms 10816 KB Output is partially correct
3 Partially correct 68 ms 10800 KB Output is partially correct
4 Partially correct 62 ms 11616 KB Output is partially correct
5 Partially correct 67 ms 12568 KB Output is partially correct
6 Partially correct 81 ms 12544 KB Output is partially correct
7 Partially correct 67 ms 12432 KB Output is partially correct
8 Partially correct 75 ms 12216 KB Output is partially correct
9 Partially correct 56 ms 10832 KB Output is partially correct
10 Partially correct 64 ms 12224 KB Output is partially correct
11 Partially correct 63 ms 11968 KB Output is partially correct
12 Partially correct 55 ms 11088 KB Output is partially correct
13 Partially correct 57 ms 11320 KB Output is partially correct
14 Partially correct 58 ms 11448 KB Output is partially correct
15 Partially correct 58 ms 11480 KB Output is partially correct
16 Partially correct 2 ms 596 KB Output is partially correct
17 Correct 45 ms 6676 KB Output is correct
18 Partially correct 57 ms 11020 KB Output is partially correct
19 Partially correct 56 ms 11004 KB Output is partially correct
20 Partially correct 78 ms 12128 KB Output is partially correct
21 Partially correct 63 ms 11900 KB Output is partially correct
22 Partially correct 65 ms 12000 KB Output is partially correct