Submission #96146

#	Time	Username	Problem	Language	Result	Execution time	Memory
96146		bogdan10bos	Mechanical Doll (IOI18_doll)	C++14	85.55 / 100	178 ms	11196 KiB

doll

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

using namespace std;

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

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 old = l;
    while( (l & (l - 1)) != 0 )
        l++;
    int mns = l - old;

    newv.clear();
    newv.resize(l);
    pos.clear();
    pos.resize(l);
    where.clear();
    where.resize(l);
    int lg = 0;
    for(lg = 0; (1 << lg) < l; lg++);
    for(int i = 0; i < l; i++)
    {
        int msk = i;
        int rmsk = 0;
        for(int j = 0; j < lg; j++)
            if((msk >> j) & 1)
                rmsk |= (1 << (lg - j - 1));
        pos[rmsk] = i;
        where[i] = rmsk;
    }
    vector<int> poss;
    for(int i = mns; i < l; i++)
        poss.push_back(pos[i]);
    sort(begin(poss), end(poss));
    for(int i = 0; i < old; i++)
        newv[ where[ poss[i] ] ] = v[i];
    for(int i = 0; i < mns; i++)
        newv[i] = -S;

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

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