Submission #240788

#	Time	Username	Problem	Language	Result	Execution time	Memory
240788		Ruxandra985	Mechanical Doll (IOI18_doll)	C++14	37 / 100	160 ms	28512 KiB

doll

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

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