Submission #1244984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244984		Boas	Mechanical Doll (IOI18_doll)	C++20	53 / 100	106 ms	15724 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

int INF = 1e9;
int swi(int x)
{
    return -x - 1;
}

void create_circuit(int M, vi A)
{
    int N = sz(A);

    const int L = __lg(N) + 2;
    vvi trees(L);
    for (int i = 1, cnt = 2; i < L; i++)
    {
        // cnt - 1 switches indexed 1 .. cnt-1
        vb x(cnt);
        while (sz(trees[i]) < cnt)
        {
            int j = 1;
            while (j < cnt)
            {
                x[j].flip();
                if (!x[j])
                    j = 2 * j + 1;
                else
                    j *= 2;
            }
            trees[i].pb(j - cnt);
        }
        cnt *= 2;
    }
    vvi nxt(M + 1); // volgende
    A.pb(0);
    loop(N, ix)
    {
        nxt[A[ix]].pb(A[ix + 1]);
    }

    vi C(M + 1, -1);
    C[0] = A[0];
    int S = 0;
    vi X, Y;
    vi curOcc(M + 1);
    loop(N, i)
    {
        if (sz(nxt[A[i]]) == 1)
        {
            C[A[i]] = A[i + 1];
        }
        else
        {
            if (curOcc[A[i]] == 0)
            {
                int log = 1;
                int power = 2;
                int k = sz(nxt[A[i]]);
                while (power < k)
                {
                    log++;
                    power *= 2;
                }
                int startIx = S;
                S += power - 1;
                loop(power - 1, ix)
                {
                    X.pb({});
                    Y.pb({});
                }
                C[A[i]] = swi(startIx);

                const auto &perm = trees[log];
                vector<int *> leaves;
                for (int ix = 0; ix < power - 1; ix++)
                {
                    int iy = ix + startIx;
                    int l = 2 * ix + 1, r = 2 * ix + 2;
                    X[iy] = swi(l + startIx), Y[iy] = swi(r + startIx);
                    if (ix >= power / 2 - 1)
                    {
                        leaves.push_back(&X[iy]);
                        leaves.push_back(&Y[iy]);
                    }
                }
                for (auto l : leaves)
                    *l = swi(startIx);
                for (int ix = 0; ix < k - 1; ++ix)
                {
                    int want = perm[ix];
                    *leaves[want] = nxt[A[i]][ix];
                }
                *leaves.back() = nxt[A[i]].back();
            }
        }
        curOcc[A[i]]++;
    }
    for (int &i : C)
        if (i == -1 && S == 0)
            i = 0;
    for (int i : C)
        if (i < -S || i > M)
            throw;
    for (int i : X)
        if (i < -S || i > M)
            throw;
    for (int i : Y)
        if (i < -S || i > M)
            throw;
    answer(C, X, Y);
}

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