Submission #601542

#	Time	Username	Problem	Language	Result	Execution time	Memory
601542		Hanksburger	Mechanical Doll (IOI18_doll)	C++17	100 / 100	82 ms	10796 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> v, w, ww, c, x, y;
void f(int u, int p, int l, int r, int z)
{
    if (l+1==r)
    {
        if (l>=z)
            x[u-1]=v[l-z];
        else
            x[u-1]=-p;
        if (r>=z)
            y[u-1]=v[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, 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, m+1, r, z);
    }
    else
        y[u-1]=-p;
}
void create_circuit(int m, vector<int> a)
{
    for (int i:a)
        v.push_back(i);
    v.push_back(0);
    int sz=v.size();
    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[j];
    v=ww;
    x.push_back(0);
    y.push_back(0);
    int u=x.size();
    f(u, u, 0, num-1, num-sz);
    for (int i=0; i<=m; i++)
        c.push_back(-u);
    answer(c, x, y);
}

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