Submission #847228

#	Time	Username	Problem	Language	Result	Execution time	Memory
847228		12345678	Mechanical Doll (IOI18_doll)	C++17	100 / 100	91 ms	12472 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+1000;
int cnt, mx, used, id, t;
vector<int> v, X(nx), Y(nx), nv;

void add(int idx, int layer)
{
    used=max(used, idx);
    if (layer==mx)
    {
        if (cnt>=1) Y[idx-1]=v[cnt--], X[idx-1]=v[cnt--];
        else if (cnt==0) Y[idx-1]=v[cnt--], X[idx-1]=-1;
    }
    else
    {
        int sid=id+1;
        add(++id, layer+1);
        Y[idx-1]=-sid;
        sid=id+1;
        if (cnt>=0) add(++id, layer+1), X[idx-1]=-sid;
        else X[idx-1]=-1;
    }
}

void create_circuit(int M, std::vector<int> A) {
    vector<int> C(M+1);
    for (int i=0; i<=M; i++) C[i]=-1;
    v=A;
    v.push_back(0);
    int N=v.size();
    cnt=N-1; mx=ceil(log2(N));
    nv.resize(N);
    reverse(v.begin(), v.end());
    for (int i=0; i<(1<<mx); i++)
    {
        int vl=0;
        for (int j=mx-1; j>=0; j--)
        {
            if ((i/(1<<j))%2!=0) vl+=(1<<(mx-j-1));
        }
        if (vl<N) nv[vl]=v[t++];
    }
    v=nv;
    reverse(v.begin(), v.end());
    add(++id, 1);
    X.resize(used); Y.resize(used);
    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