Submission #611906

#	Time	Username	Problem	Language	Result	Execution time	Memory
611906		hibiki	Mechanical Doll (IOI18_doll)	C++11	53 / 100	126 ms	18040 KiB

doll

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

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

int pw2[32];
vector<int> nxt[100005], c, x, y;

int seat = -1;
int dfs(int val, int lv, int mlv, int head)
{
    if (lv == mlv)
    {
        if (nxt[head][val] == -1)
            return -seat;
        return nxt[head][val];
    }
    pair<int, int> ret;
    ret.f = dfs(val, lv + 1, mlv, head);
    ret.s = dfs(val + pw2[lv], lv + 1, mlv, head);
    if (lv)
    {
        if (ret.f == ret.s)
            return ret.f;
        x.pb(ret.f);
        y.pb(ret.s);
        return -sz(x);
    }
    else
    {
        x[seat - 1] = ret.f;
        y[seat - 1] = ret.s;
        return -seat;
    }
}

void create_circuit(int m, vector<int> a)
{
    int n = sz(a);
    pw2[0] = 1;
    for (int i = 1; i < 32; i++)
        pw2[i] = pw2[i - 1] * 2;

    nxt[0].pb(a[0]);
    for (int i = 0; i < n - 1; i++)
        nxt[a[i]].pb(a[i + 1]);
    nxt[a[n - 1]].pb(0);

    c.pb(nxt[0][0]);
    for (int i = 1; i <= m; i++)
    {
        if (nxt[i].empty())
        {
            c.pb(i);
            continue;
        }

        if (sz(nxt[i]) == 1)
        {
            c.pb(nxt[i][0]);
            continue;
        }

        int mlv = ceil(log2(sz(nxt[i])));
        int msz = pw2[mlv];

        vector<int> temp;
        for (int j = 0; j < msz - sz(nxt[i]); j++)
            temp.pb(-1);
        for (auto val : nxt[i])
            temp.pb(val);
        nxt[i] = temp;

        x.pb(-1);
        y.pb(-1);
        seat = sz(x);
        c.pb(dfs(0, 0, mlv, i));
    }

    answer(c, x, y);
}

• 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