Submission #571704

#	Time	Username	Problem	Language	Result	Execution time	Memory
571704		Hanksburger	Mechanical Doll (IOI18_doll)	C++17	100 / 100	79 ms	12664 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> c, x, y;
int b[400005];
void recur(int l, int r, int p, bool q)
{
    if (b[r]<0 || l==r)
    {
        if (q)
            y[p-1]=b[r];
        else
            x[p-1]=b[r];
        return;
    }
    x.push_back(0);
    y.push_back(0);
    int num=x.size();
    if (q)
        y[p-1]=-num;
    else
        x[p-1]=-num;
    int mid=(l+r)/2;
    recur(l, mid, num, 0);
    recur(mid+1, r, num, 1);
}
void create_circuit(int m, vector<int> a)
{
    a.push_back(0);
    x.push_back(0);
    y.push_back(0);
    int sz=a.size();
    int loog=log2(sz-0.5)+1;
    int power=(1<<loog);
    int cnt=0;
    for (int i=0; i<power; i++)
    {
        int cur=0;
        for (int j=0; j<loog; j++)
            if (i&(1<<j))
                cur+=(1<<(loog-j-1));
        if (cur>=power-sz)
        {
            b[cur]=a[cnt];
            cnt++;
        }
        else
            b[cur]=-1;
    }
    recur(0, power/2-1, 1, 0);
    recur(power/2, power-1, 1, 1);
    for (int i=0; i<=m; i++)
        c.push_back(-1);
    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