Submission #1014956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014956		ThegeekKnight16	Mechanical Doll (IOI18_doll)	C++17	100 / 100	97 ms	10068 KiB

doll

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

int build(int qnt, int &extra, vector<int> &X, vector<int> &Y)
{
    if (qnt == 1) return 0;
    if (qnt <= extra)
    {
        extra -= qnt;
        return -1;
    }
    X.push_back(-1); Y.push_back(-1);
    int id = X.size();

    int e = build(qnt/2, extra, X, Y), d = build(qnt/2, extra, X, Y);
    X[id-1] = e, Y[id-1] = d;
    return -id;
}

void create_circuit(int M, std::vector<int> A)
{
    int N = A.size();
    if (N == 1)
    {
        vector<int> C = {A[0], 0};
        vector<int> X, Y;
        answer(C, X, Y);
        return;
    }
    vector<int> X, Y;
    int qnt = 1;
    while (qnt < N) qnt *= 2;
    int extra = qnt - N;
    bool delay = 0;
    if (extra % 2) extra--, delay = 1;
    build(qnt, extra, X, Y);

    vector<int> C(M+1, -1); C[0] = (delay ? -1 : A[0]);
    vector<int> state(X.size());
    for (int i = 1-(int)delay; i < N; i++)
    {
        int id = -1;
        while (id < 0)
        {
            int nextId = (state[-id-1] ? Y[-id-1] : X[-id-1]);
            state[-id-1] ^= 1;
            if (nextId == 0)
            {
                if (state[-id-1]) X[-id-1] = A[i];
                else Y[-id-1] = A[i];
                break;
            }
            id = nextId;
        }
    }
    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