oj.uz

Submission #740589

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

const int maxn = 2e5 + 10;

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

struct state
{
    int dev, lf_child, rf_child;
    vector < int > fin;

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

void create_node(int v)
{
    if (g[v].size() == 0)
        return;

    if (g[v].size() == 1)
    {
        c[v] = g[v][0];
        return;
    }
    int nec = 2, st = 0;
    while(nec < g[v].size())
        nec *= 2, st ++;
    ///cout << g[v].size() << " " << nec << " : " << st << endl;
    vector < state > gen;
    int sz = x.size();
    state it;
    it.dev = ++ sz;
    c[v] = -it.dev;
    it.fin.push_back(1);
    gen.push_back(it);
    for (int step = 0; step < st; step ++)
    {
        vector < state > new_gen;
        for (int i = 0; i < gen.size(); i ++)
        {
            state new_state;
            new_state.dev = ++ sz;
            gen[i].lf_child = - new_state.dev;
            for (int cur : gen[i].fin)
                new_state.fin.push_back(cur);
            new_gen.push_back(new_state);
            new_state = state();

            new_state.dev = ++ sz;
            gen[i].rf_child = - new_state.dev;
            for (int cur : gen[i].fin)
                new_state.fin.push_back(cur + (1 << step));
            new_gen.push_back(new_state);
        }
        for (state cur : gen)
        {
            x.push_back(cur.lf_child);
            y.push_back(cur.rf_child);
        }
        gen = new_gen;
    }
    ///cout << "fine" << endl;
    int offset = gen.size() * 2 - g[v].size();
    int to = 0;

    vector < int > vec;
    for (int i = gen.size() - 1; i >= 0; i --)
    {
int lf_path = gen[i].fin[0], rf_path = gen[i].fin[0] + (1 << st);
if (vec.size() < g[v].size())
    vec.push_back(rf_path);
if (vec.size() < g[v].size())
    vec.push_back(lf_path);
    }

    sort(vec.begin(), vec.end());
    map < int, int > mp;
    for (int i = 0; i < vec.size(); i ++)
    {
        mp[vec[i]] = i + 1;
    }
    for (int i = 0; i < gen.size(); i ++)
    {
        ///cout << gen[i].fin.size() << endl;
        int lf_path = gen[i].fin[0], rf_path = gen[i].fin[0] + (1 << st);
        if (mp[lf_path] == 0)
            x.push_back(-it.dev);
        else
            x.push_back(g[v][mp[lf_path] - 1]);
        if (mp[rf_path] == 0)
            y.push_back(-it.dev);
        else
            y.push_back(g[v][mp[rf_path] - 1]);


        ///cout << v << " :: " << lf_path << " : " << rf_path << endl;
        /**if (to < g[v].size())
            x.push_back(g[v][to] ++);
        else
            x.push_back(- it.dev);
        if (rf_path > offset)
            y.push_back(g[v][rf_path - offset - 1]);
        else
            y.push_back(-it.dev);*/
    }
}
void create_circuit(int M, vector<int> A)
{
    n = A.size();
    m = M;

    c.resize(m + 1);
    g[0].push_back(A[0]);
    for (int i = 1; i < A.size(); i ++)
    {
        g[0].push_back(A[i]);
    }
    g[0].push_back(0);
    create_node(0);
    for (int i = 0; i <= m; i ++)
        c[i] = -1;
    /**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_node(int)':
doll.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while(nec < g[v].size())
      |           ~~~~^~~~~~~~~~~~~
doll.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int i = 0; i < gen.size(); i ++)
      |                         ~~^~~~~~~~~~~~
doll.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < vec.size(); i ++)
      |                     ~~^~~~~~~~~~~~
doll.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<state>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < gen.size(); i ++)
      |                     ~~^~~~~~~~~~~~
doll.cpp:73:9: warning: unused variable 'offset' [-Wunused-variable]
   73 |     int offset = gen.size() * 2 - g[v].size();
      |         ^~~~~~
doll.cpp:74:9: warning: unused variable 'to' [-Wunused-variable]
   74 |     int to = 0;
      |         ^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:124:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int i = 1; i < A.size(); i ++)
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4884 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 3 ms 4948 KB Output is partially correct
2 Partially correct 241 ms 31092 KB Output is partially correct
3 Partially correct 230 ms 31124 KB Output is partially correct
4 Partially correct 334 ms 31860 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4948 KB Output is partially correct
2 Partially correct 241 ms 31092 KB Output is partially correct
3 Partially correct 230 ms 31124 KB Output is partially correct
4 Partially correct 334 ms 31860 KB Output is partially correct
5 Partially correct 324 ms 32040 KB Output is partially correct
6 Partially correct 335 ms 31960 KB Output is partially correct
7 Partially correct 323 ms 32080 KB Output is partially correct
8 Partially correct 362 ms 32008 KB Output is partially correct
9 Partially correct 263 ms 31120 KB Output is partially correct
10 Partially correct 349 ms 31996 KB Output is partially correct
11 Partially correct 317 ms 31864 KB Output is partially correct
12 Partially correct 239 ms 31120 KB Output is partially correct
13 Partially correct 235 ms 31144 KB Output is partially correct
14 Partially correct 239 ms 31152 KB Output is partially correct
15 Partially correct 244 ms 31252 KB Output is partially correct
16 Partially correct 8 ms 5808 KB Output is partially correct
17 Correct 132 ms 19308 KB Output is correct
18 Partially correct 261 ms 31116 KB Output is partially correct
19 Partially correct 237 ms 31168 KB Output is partially correct
20 Partially correct 307 ms 31960 KB Output is partially correct
21 Partially correct 316 ms 31888 KB Output is partially correct
22 Partially correct 339 ms 31888 KB Output is partially correct