Submission #293246

#	Time	Username	Problem	Language	Result	Execution time	Memory
293246		SamAnd	Mechanical Doll (IOI18_doll)	C++17	100 / 100	235 ms	25804 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], vi[N];
int q;
int f;
int bil(int l, int r, int pos, int d)
{
    if (r < q)
    {
      	return f;
        --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;
    ansx[-u - 1] = bil(l, m, pos, d + 1);
    ansy[-u - 1] = bil(m + 1, r, pos + (1 << d), d + 1);
    return u;
}
 
bool c[N];
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);
        vi[A[i]].push_back(i);
    }
 
    for (int i = 1; i <= m; ++i)
    {
        if (sz(v[i]) == 1)
        {
            --n;
            c[vi[i][0]] = true;
        }
    }
 
    if (n == 0)
    {
        ans.push_back(A[0]);
        for (int x = 1; x <= m; ++x)
        {
            if (sz(v[x]) == 1)
                ans.push_back(v[x][0]);
            else
                ans.push_back(0);
        }
        answer(ans, ansx, ansy);
        return;
    }
 
    while (!stg0(q + n))
        ++q;
    bil(0, q + n - 1, 0, 0);
    vector<pair<int, pair<int, int> > > vv;
    for (int i = 0; i < sz(ansx); ++i)
    {
        if (ansx[i] >= 0)
            vv.push_back(m_p(ansx[i], m_p(i, 0)));
        if (ansy[i] >= 0)
            vv.push_back(m_p(ansy[i], m_p(i, 1)));
    }
    sort(all(vv));
 
    assert(sz(vv) == n);
    int j = 0;
    for (int i = 0; i < n; ++i)
    {
        while (c[j])
            ++j;
        if (j < sz(A) - 1)
        {
            if (vv[i].se.se == 0)
                ansx[vv[i].se.fi] = A[j + 1];
            else
                ansy[vv[i].se.fi] = A[j + 1];
        }
        else
        {
            if (vv[i].se.se == 0)
                ansx[vv[i].se.fi] = 0;
            else
                ansy[vv[i].se.fi] = 0;
        }
        ++j;
    }
 
    n = sz(A);
    ans.push_back(A[0]);
    for (int x = 1; x <= m; ++x)
    {
        if (sz(v[x]) == 1)
            ans.push_back(v[x][0]);
        else
            ans.push_back(f);
    }
    answer(ans, ansx, ansy);
}

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