Submission #1216591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216591		the_coding_pooh	Mechanical Doll (IOI18_doll)	C++20	100 / 100	75 ms	10904 KiB

doll

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

using namespace std;

vector <int> X, Y;

const int TEMP1 = 712271227, TEMP2 = 1e9 + 7;

int build_cbt(int N, int d){
    if(d == 0)
        return TEMP1;
    int l, r;
    if (N <= (1 << (d - 1)))
        r = build_cbt(N, d - 1), l = TEMP2;
    else
        r = build_cbt((1 << (d - 1)), d - 1), l = build_cbt(N - (1 << (d - 1)), d - 1);
    X.push_back(l);
    Y.push_back(r);
    uwu - ((int)X.size());
}

const int SIZE = 2e5 + 5;

vector <int> tmpA;

bitset <SIZE> status;

int cnt = 0, head;

void simulate(int id){
    if(cnt >= (int)tmpA.size())
        uwu;
    int rid = (-id) - 1;
    status[rid] = !status[rid];
    if (status[rid]){
        if(X[rid] == TEMP1){
            X[rid] = tmpA[cnt];
            cnt++;
            simulate(head);
            uwu;
        }
        else if(X[rid] == TEMP2){
            X[rid] = head;
            simulate(head);
            uwu;
        }
        simulate(X[rid]);
        uwu;
    }
    else{
        if(Y[rid] == TEMP1){
            Y[rid] = tmpA[cnt];
            cnt++;
            simulate(head);
            uwu;
        }
        else if(Y[rid] == TEMP2){
            Y[rid] = head;
            simulate(head);
            uwu;
        }
        simulate(Y[rid]);
        uwu;
    }
    uwu;
}

void create_circuit(int M, vector<int> A) {
    vector<int> C(M + 1);
    A.push_back(0);
    tmpA = A;
    int N = A.size();
    int d = __lg(N - 1) + 1;
    X.clear(), Y.clear();
    int id = build_cbt(N, d);
    C[0] = id;
    for (int i = 1; i <= M; ++i) {
        C[i] = id;
    }
    head = id;
    cnt = 0;
    status.reset();
    simulate(head);
    assert(status.count() == 0);
    answer(C, X, Y);
    uwu;
}

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