Submission #96140

#	Time	Username	Problem	Language	Result	Execution time	Memory
96140		bogdan10bos	Mechanical Doll (IOI18_doll)	C++14	6 / 100	111 ms	11428 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

int S;
vector<int> X, Y;

int make_switch(vector<int> left, vector<int> right)
{
    if(left.size() != right.size()) return -(1 << 30);
    if(left.size() == 1)
    {
        S++;
        X.push_back(left[0]);
        Y.push_back(right[0]);
        return -S;
    }

    S++;
    int id = S;
    X.push_back(0);
    Y.push_back(0);

    int l;
    vector<int> lft, rgt;

    l = left.size();
    lft.clear(); rgt.clear();
    for(int i = 0; i < l / 2; i++)
        lft.push_back(left[i]);
    for(int i = l / 2; i < l; i++)
        rgt.push_back(left[i]);
    int sl = make_switch(lft, rgt);

    l = right.size();
    lft.clear(); rgt.clear();
    for(int i = 0; i < l / 2; i++)
        lft.push_back(right[i]);
    for(int i = l / 2; i < l; i++)
        rgt.push_back(right[i]);
    int sr = make_switch(lft, rgt);

    X[id - 1] = sl;
    Y[id - 1] = sr;
    return -id;
}

int make_switch(vector<int> v)
{
    if(v.empty())   return 0;
    if(v.size() == 1)
        return v[0];

    int l = v.size();
    assert( (l & (l - 1)) == 0 );

    vector<int> newv;
    newv.resize(v.size());
    int lg = 0;
    for(lg = 0; (1 << lg) < v.size(); lg++);
    for(int i = 0; i < v.size(); i++)
    {
        int msk = i;
        int rmsk = 0;
        for(int j = 0; j < lg; j++)
            if((msk >> j) & 1)
                rmsk |= (1 << (lg - j - 1));
        newv[rmsk] = v[i];
    }

    vector<int> lft, rgt;
    for(int i = 0; i < l / 2; i++)
        lft.push_back(newv[i]);
    for(int i = l / 2; i < l; i++)
        rgt.push_back(newv[i]);
    return make_switch(lft, rgt);
}

void create_circuit(int M, vector<int> A)
{
    vector< vector<int> > v;
    v.resize(M + 2);
    int lst = 0;
    for(int i = 0; i < A.size(); i++)
    {
        v[lst].push_back(A[i]);
        lst = A[i];
    }
    v[lst].push_back(0);

    vector<int> ex;
    ex.resize(M + 1);
    X.clear(), Y.clear();

    S = 0;
    for(int i = 0; i <= M; i++)
    {
        int l = v[i].size();
        ex[i] = make_switch(v[i]);
    }

    answer(ex, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'int make_switch(std::vector<int>)':
doll.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(lg = 0; (1 << lg) < v.size(); lg++);
      |                 ~~~~~~~~~~^~~~~~~~~~
doll.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0; i < A.size(); i++)
      |                    ~~^~~~~~~~~~
doll.cpp:99:13: warning: unused variable 'l' [-Wunused-variable]
   99 |         int l = v[i].size();
      |             ^

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