Submission #292285

#	Time	Username	Problem	Language	Result	Execution time	Memory
292285		SamAnd	Mechanical Doll (IOI18_doll)	C++17	16.31 / 100	153 ms	18320 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 200005;

int n, m;

int z;
vector<int> ans;
vector<int> ansx;
vector<int> ansy;

bool stg0(int x)
{
    while (x % 2 == 0)
        x /= 2;
    return x == 1;
}

vector<int> v[N];
int q;
int f;
int bil(int l, int r, int pos, int d, int x)
{
    if (r < q)
    {
        --z;
        ansx.push_back(z);
        ansy.push_back(f);
        return z;
    }
    if (l == r)
    {
        return pos;
    }
    int m = (l + r) / 2;
    int u = --z;
    ansx.push_back(0);
    ansy.push_back(0);
    if (d == 0)
        f = u;
    int uu = bil(l, m, pos, d + 1, x);
    ansx[-u - 1] = uu;
    uu = bil(m + 1, r, pos + (1 << d), d + 1, x);
    ansy[-u - 1] = uu;
    return u;
}

void create_circuit(int M_, std::vector<int> A)
{
    n = sz(A);
    m = M_;

    for (int i = 0; i < n; ++i)
    {
        if (i < n - 1)
            v[A[i]].push_back(A[i + 1]);
        else
            v[A[i]].push_back(0);
    }

    ans.push_back(A[0]);
    for (int x = 1; x <= m; ++x)
    {
        if (v[x].empty())
        {
            ans.push_back(0);
            continue;
        }
        else if (sz(v[x]) == 1)
        {
            ans.push_back(v[x][0]);
            continue;
        }
        reverse(all(v[x]));
        q = 0;
        while (!stg0(sz(v[x]) + q))
        {
            ++q;
        }
        reverse(all(v[x]));
        int s = sz(ansx);
        int u = bil(0, sz(v[x]) + q - 1, 0, 0, x);
        vector<pair<int, int> > vv;
        for (int i = s; i < sz(ansx); ++i)
        {
            if (ansx[i] >= 0)
                vv.push_back(m_p(ansx[i], i));
            if (ansy[i] >= 0)
                vv.push_back(m_p(ansy[i], i));
        }
        sort(all(vv));
        assert(sz(vv) == sz(v[x]));
        for (int i = 0; i < sz(v[x]); ++i)
        {
            if (ansx[vv[i].se] == vv[i].fi)
                ansx[vv[i].se] = v[x][i];
            else
                ansy[vv[i].se] = v[x][i];
        }
        ans.push_back(u);
    }
    answer(ans, ansx, ansy);
}

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