Submission #240173

#	Time	Username	Problem	Language	Result	Execution time	Memory
240173		Ruxandra985	Mechanical Doll (IOI18_doll)	C++14	0 / 100	7 ms	9712 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 (int nod , int conf , int p2 , int val , vector<int> a){

    int i , vecin , cnt;

    if (2 * nod > val){
        if (conf < a.size())
            w[nod].push_back(-a[conf]);
        else if (conf == val){
            w[nod].push_back(0);
            //previous = nod;
        }
        else w[nod].push_back(1);



        if (conf + p2 < a.size())
            w[nod].push_back(-a[conf]);
        else if (conf + p2 == val){
            w[nod].push_back(0);
            //previous = nod;
        }
        else w[nod].push_back(1);
        /// altfel, e o frunza irelevanta
    }
    else {
        dfs(2 * nod , conf , p2 * 2 , val , a);
        dfs(2 * nod + 1 , conf + p2 , p2 * 2 , val , a);


        /// aici trb sa vad daca elimin vreun fiu

        /*cnt = 0;

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

            if (w[vecin].size() == 1){ /// vecin e useless
                cnt++;
            }
            else if (w[vecin].empty()) {
                printf ("nu ma asteptam la asta:)");
            }

        }

        if (cnt == 2){ /// elimini ambele
            for (i = 0 ; i < w[nod].size() ; i++){
                vecin = w[nod][i];

                if (w[vecin].size() == 1){ /// vecin e useless
                    w[nod][i] = w[vecin][0];
                }
                else if (w[vecin].empty()) {
                    printf ("nu ma asteptam la asta:)");
                }

            }
        }
        else if (cnt == 1){

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

                if (w[vecin].size() == 1){ /// vecin e useless, dar nu poti sa il elim
                    w[ vecin ].push_back(0);

                    if (w[previous][0] == 0)
                        w[previous][0] = -1;
                    else w[previous[1] = -1;

                    previous = vecin;
                }
                else if (w[vecin].empty()) {
                    printf ("nu ma asteptam la asta:)");
                }

            }

        }*/



    }

}


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;
    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);

        }

    }

    dfs (1 , 0 , 1 , (1 << l) - 1 , a);

    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(int, int, int, int, std::vector<int>)':
doll.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         if (conf < a.size())
      |             ~~~~~^~~~~~~~~~
doll.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         if (conf + p2 < a.size())
      |             ~~~~~~~~~~^~~~~~~~~~
doll.cpp:12:9: warning: unused variable 'i' [-Wunused-variable]
   12 |     int i , vecin , cnt;
      |         ^
doll.cpp:12:13: warning: unused variable 'vecin' [-Wunused-variable]
   12 |     int i , vecin , cnt;
      |             ^~~~~
doll.cpp:12:21: warning: unused variable 'cnt' [-Wunused-variable]
   12 |     int i , vecin , cnt;
      |                     ^~~
doll.cpp: In function 'void dfs_put(int)':
doll.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (i = 0 ; i < w[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
doll.cpp: In function 'void dfs_solve(int)':
doll.cpp:129:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (i = 0 ; i < w[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56