Submission #601531

#	Time	Username	Problem	Language	Result	Execution time	Memory
601531		Hanksburger	Mechanical Doll (IOI18_doll)	C++17	85.55 / 100	98 ms	15876 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> v[100005], w, ww, c, x, y;
void f(int u, int p, int i, int l, int r, int z)
{
    if (l+1==r)
    {
        if (l>=z)
            x[u-1]=v[i][l-z];
        else
            x[u-1]=-p;
        if (r>=z)
            y[u-1]=v[i][r-z];
        else
            y[u-1]=-p;
        return;
    }
    int m=(l+r)/2;
    if (m>=z)
    {
        x.push_back(0);
        y.push_back(0);
        int U=x.size();
        x[u-1]=-U;
        f(U, p, i, l, m, z);
    }
    else
        x[u-1]=-p;
    if (r>=z)
    {
        x.push_back(0);
        y.push_back(0);
        int U=x.size();
        y[u-1]=-U;
        f(U, p, i, m+1, r, z);
    }
    else
        y[u-1]=-p;
}
void create_circuit(int m, vector<int> a)
{
    a.push_back(0);
    for (int i=1; i<a.size(); i++)
        v[a[i-1]].push_back(a[i]);
    c.push_back(a[0]);
    for (int i=1; i<=m; i++)
    {
        int sz=v[i].size();
        if (!sz)
            c.push_back(0);
        else if (sz==1)
            c.push_back(v[i][0]);
        else
        {
            int loog=log2(sz-0.5)+1;
            int num=1<<loog;
            w.clear();
            ww.clear();
            for (int j=0; j<num; j++)
            {
                int sum=0;
                for (int k=0; k<loog; k++)
                    if (j&(1<<k))
                        sum+=1<<(loog-k-1);
                if (sum>=num-sz)
                    w.push_back(sum-num+sz);
            }
            for (int j=0; j<sz; j++)
                ww.push_back(0);
            for (int j=0; j<sz; j++)
                ww[w[j]]=v[i][j];
            v[i]=ww;
            x.push_back(0);
            y.push_back(0);
            int u=x.size();
            c.push_back(-u);
            f(u, u, i, 0, num-1, num-sz);
        }
    }
    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i=1; i<a.size(); i++)
      |                   ~^~~~~~~~~

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