oj.uz

Submission #240788

# Submission time Handle Problem Language Result Execution time Memory
240788 2020-06-21T07:49:24 Z Ruxandra985 Mechanical Doll (IOI18_doll) C++14
37 / 100
 160 ms 28512 KB 
#include <bits/stdc++.h>
#include "doll.h"
using namespace std;


vector <int> x , y , w[400010];

int v[400010] , elem , newp[400010] , previous;

void dfs_put (int nod){

    int i , vecin;

    if (nod < 1){

        return;

    }

    v[++elem] = nod;

    for (i = 0 ; i < w[nod].size() ; i++){
        vecin = w[nod][i];

        if (vecin != 1)
            dfs_put(vecin);

    }

}

void dfs_solve (int nod){

    int i , vecin , val;

    if (nod < 1){

        return;

    }

    for (i = 0 ; i < w[nod].size() ; i++){
        vecin = w[nod][i];

        if (vecin > 0)
            vecin = newp[vecin];

        val = -vecin;

        if (i == 0)
            x[ newp[nod] - 1 ] = val;
        else y[ newp[nod] - 1 ] = val;

        if (vecin != 1)
            dfs_solve(vecin);

    }

    //if (x.size() != y.size())
      //  printf ("!!!!!!!");

    if (w[nod].size() != 2){
        printf ("w[nod] nu are size 2");
    }

}


void create_circuit(int m, vector<int> a) {
    int n = a.size() , i , l , aux , conf;
    vector <int> c;

    c.push_back(-1);

    for (i = 1 ; i <= m ; i++)
        c.push_back(-1);

    /// trb sa vezi cate noduri nu iti sunt necesare

    l = 0;
    while ((1 << l) <= n){
        l++;
    }

    //l++;

    for (i = 1 ; i <= (1 << l) - 1 ; i++){

        if (2 * i <= (1 << l) - 1){

            w[i].push_back(2 * i);
            w[i].push_back(2 * i + 1);

        }

    }

    for (i = 1 ; i <= (1 << l) - 1 ; i++){

        //if (i == 8)
          //  printf ("a");

        if (2 * i > (1 << l) - 1){

            aux = 2 * i;
            conf = 0;

            while (aux){
                conf = conf * 2 + (aux % 2);
                aux /= 2;
            }

            conf /= 2;

            if (conf < a.size())
                w[i].push_back(-a[conf]);
            else if (conf == (1 << l) - 1){
                w[i].push_back(0);
            }
            else w[i].push_back(1);

            /// -----------------------------------

            aux = 2 * i + 1;
            conf = 0;

            while (aux){
                conf = conf * 2 + (aux % 2);
                aux /= 2;
            }

            conf /= 2;

            if (conf < a.size())
                w[i].push_back(-a[conf]);
            else if (conf == (1 << l) - 1){
                w[i].push_back(0);
            }
            else w[i].push_back(1);


        }

    }

    dfs_put (1);

    sort (v + 1 , v + elem + 1);

    for (i = 1 ; i <= elem ; i++){
        newp[v[i]] = i;
    }

    x.resize(elem , 0);
    y.resize(elem , 0);

    dfs_solve (1);

    //for (i = 0 ; i < x.size() ; i++){
      //  printf ("%d %d\n" , x[i] , y[i]);
    //}

    answer (c , x , y);

}

Compilation message

doll.cpp: In function 'void dfs_put(int)':
doll.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (i = 0 ; i < w[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
doll.cpp: In function 'void dfs_solve(int)':
doll.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (i = 0 ; i < w[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             if (conf < a.size())
      |                 ~~~~~^~~~~~~~~~
doll.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             if (conf < a.size())
      |                 ~~~~~^~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9676 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 8 ms 9708 KB Output is partially correct
2 Partially correct 132 ms 27224 KB Output is partially correct
3 Partially correct 136 ms 27192 KB Output is partially correct
4 Partially correct 142 ms 27676 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 9708 KB Output is partially correct
2 Partially correct 132 ms 27224 KB Output is partially correct
3 Partially correct 136 ms 27192 KB Output is partially correct
4 Partially correct 142 ms 27676 KB Output is partially correct
5 Partially correct 150 ms 28436 KB Output is partially correct
6 Partially correct 144 ms 28372 KB Output is partially correct
7 Partially correct 153 ms 28512 KB Output is partially correct
8 Partially correct 160 ms 28180 KB Output is partially correct
9 Partially correct 135 ms 27204 KB Output is partially correct
10 Partially correct 148 ms 28120 KB Output is partially correct
11 Partially correct 142 ms 27724 KB Output is partially correct
12 Partially correct 139 ms 27456 KB Output is partially correct
13 Partially correct 138 ms 27848 KB Output is partially correct
14 Partially correct 138 ms 27888 KB Output is partially correct
15 Partially correct 141 ms 28020 KB Output is partially correct
16 Partially correct 11 ms 10188 KB Output is partially correct
17 Correct 77 ms 18884 KB Output is correct
18 Partially correct 131 ms 27360 KB Output is partially correct
19 Partially correct 133 ms 27448 KB Output is partially correct
20 Partially correct 150 ms 28012 KB Output is partially correct
21 Partially correct 141 ms 27692 KB Output is partially correct
22 Partially correct 148 ms 27860 KB Output is partially correct