Submission #96144

#	Time	Username	Problem	Language	Result	Execution time	Memory
96144		bogdan10bos	Mechanical Doll (IOI18_doll)	C++14	53 / 100	153 ms	14716 KiB

doll

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

using namespace std;

int S;
vector<int> X, Y;
vector<int> newv;

int make_switch(int st, int dr, int idd = -1)
{
    bool ok = true;
    for(int i = st + 1; i <= dr; i++)
        if(newv[i] != newv[st])
        {
            ok = false;
            break;
        }
    if(ok)  return newv[st];
    if(st + 1 == dr)
    {
        if(idd == -1)
        {
            S++;
            X.push_back(newv[st]);
            Y.push_back(newv[dr]);
            return -S;
        }
        else
        {
            X[idd - 1] = newv[st];
            Y[idd - 1] = newv[dr];
            return -idd;
        }
    }

    int id = -1;
    if(idd == -1)
    {
        S++;
        id = S;
        X.push_back(0);
        Y.push_back(0);
    }
    else
        id = idd;

    int mij = st + (dr - st) / 2;
    int sl = make_switch(st, mij);
    int sr = make_switch(mij + 1, dr);

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

    S++;
    X.push_back(0);
    Y.push_back(0);

    int l = v.size();
    int lst = v.back();
    v.pop_back();

    while( (l & (l - 1)) != 0 )
    {
        v.push_back(-S);
        l++;
    }
    v.push_back(lst);

    newv.clear();
    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];
    }

    return make_switch(0, l - 1, S);
}

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

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