Submission #591938

#	Time	Username	Problem	Language	Result	Execution time	Memory
591938		PiejanVDC	Mechanical Doll (IOI18_doll)	C++17	6 / 100	112 ms	15540 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);


void create_circuit(int m, vector<int>a) {
    const int n = (int)a.size();
    a.push_back(0);
    
    vector<vector<int>>v(m+1);

    vector<int>C(m+1, 0);
    C[0] = a[0];
    vector<int>X,Y;

    for(int i = 0 ; i < n ; i++) {
        v[a[i]].push_back(a[i+1]);
    }

    int j = 1;

    for(int i = 1 ; i <= m ; i++) {

        //cout << i << ' ';

        if((int)v[i].size() == 0)
            continue;

        if(v[i].size() == 1) {
            C[i] = v[i][0];
            continue;
        }

        int p = 0;
        while((1 << p) < ((v[i].size())))
            p++;

        vector<int>w;
        if(1) {
            int cnt = /*(v[i].size()&1) + 2*(((v[i].size()+1)/2)&1)*/ (1 << p) - (int)v[i].size(); 
            for(int ii = 0 ; ii < v[i].size()/2 ; ii++)
                w.push_back(v[i][ii]);
            
            for(int ii = 0 ; ii < cnt ; ii++)
                w.push_back(-j);
            
            for(int ii = v[i].size() / 2 ; ii < v[i].size() ; ii++)
                w.push_back(v[i][ii]);
            v[i] = w; 
        }

        vector<int>st(8 * (v[i].size()+1)/2, 0);
        vector<int>rev(8 * (v[i].size()+1)/2);

        C[i] = -j;

        /*for(auto z : v[i])
            cout << z << ' ';*/

        //cout << i << ' ' << v[i].size() << '\n';

        for(int l = 0 ; l < v[i].size()/2 ; l++) {
            //cerr << l << ' ';
            int pos = 1, d = 0;
            while(d <= p) {
                if(d < p) {
                    if(!st[pos]) {
                        st[pos] = 1;
                        rev[pos] = j-1;
                        j++;
                        X.push_back(INT_MAX);
                        Y.push_back(INT_MAX);
                    }

                    if(st[pos] == 1) {
                        if(!st[2*pos]) {
                            X[rev[pos]] = (-(j));
                        }
                        st[pos] = 2;
                        pos *= 2;
                    } else {
                        if(!st[2*pos+1]) {
                            Y[rev[pos]] = (-(j));
                        }
                        st[pos] = 1;
                        pos *= 2;
                        pos++;
                    } 

                    d++;
                } else {
                    d++;
                    if(!st[pos]) {
                        st[pos] = 1;
                        rev[pos] = j-1;
                        j++;
                        X.push_back(INT_MAX);
                        Y.push_back(INT_MAX);
                    }
                    if(st[pos] == 1) {
                        X[rev[pos]] = v[i][l];
                        st[pos] = 2;
                    } else {
                        Y[rev[pos]] = v[i][l];
                        st[pos] = 1;
                    }
                }
            } 
        }

        // probeer toch EEN baan te maken en dan vooraleer te beantwoorden alles te checken dat nog geen verbinding heeft en die naar zichzelf laten gaan ofwel X en Y switchen 

        for(int l = v[i].size()/2 ; l < v[i].size() ; l++) {
            int pos = 1, d = 0;
            while(d <= p) {
                if(d < p) {
                    d++;
                    if(st[pos] == 1) {
                        st[pos] = 2;
                        pos *= 2;
                   } else {
                        if(!st[2*pos+1]) {
                            st[pos] = 1;
                            Y[rev[pos]] = -rev[pos] - 1; // watch
                            pos *= 2;
                            continue;
                        }
                        st[pos] = 1;
                        pos *= 2;
                        pos++;
                   }
                } else {
                    d++;
                    if(st[pos] == 1) {
                        X[rev[pos]] = -rev[pos]-1;
                        st[pos] = 2;
                    } 
                    st[pos] = 1;
                    Y[rev[pos]] = v[i][l];
                }
            }
        }
    }

    for(int i = 0 ; i < (int)X.size() ; i++) {
        if(Y[i] == INT_MAX)
            Y[i] = -i-1, swap(X[i], Y[i]);
        if(Y[i] == -i-1)
            swap(X[i], Y[i]);
    }

    /*cerr << '\n';

    for(auto z : C)
        cerr << z << ' ';
    cerr << '\n';

    for(auto z : X)
        cerr << z << ' ';
    cerr << '\n';

    for(auto z : Y)
        cerr << z << ' ';
    cerr << '\n';*/

    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:37:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while((1 << p) < ((v[i].size())))
      |               ~~~~~~~~~^~~~~~~~~~~~~~~~~
doll.cpp:43:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int ii = 0 ; ii < v[i].size()/2 ; ii++)
      |                              ~~~^~~~~~~~~~~~~~~
doll.cpp:49:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int ii = v[i].size() / 2 ; ii < v[i].size() ; ii++)
      |                                            ~~~^~~~~~~~~~~~~
doll.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int l = 0 ; l < v[i].size()/2 ; l++) {
      |                         ~~^~~~~~~~~~~~~~~
doll.cpp:115:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for(int l = v[i].size()/2 ; l < v[i].size() ; l++) {
      |                                     ~~^~~~~~~~~~~~~

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