Submission #773255

#	Time	Username	Problem	Language	Result	Execution time	Memory
773255		_martynas	Mechanical Doll (IOI18_doll)	C++11	72.60 / 100	168 ms	21708 KiB

doll

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

using namespace std;

int counter = 0;
struct Node {
    array<Node*, 2> c = {nullptr, nullptr};
    int to = 0, idx = -1;
    bool terminal() {
        return c[0] == nullptr && c[1] == nullptr;
    }
};

Node* construct(int sz, int depth) {
    if(sz <= 0) return nullptr;
    Node* root = new Node();
    if(depth <= 0) return root;
    root->idx = ++counter;
    int sz_l = 1<<(31-__builtin_clz(sz));
    if(sz_l == sz && sz > 1) sz_l /= 2;
    root->c[0] = construct(sz-sz_l, depth-1);
    root->c[1] = construct(sz_l, depth-1);
    for(auto n : root->c) {
        if(n == nullptr) continue;
    }
    return root;
}

// first time going to terminal node
void walk(Node* curr, Node* root, int target, vector<int> &X, vector<int> &Y) {
    Node* to = curr->c[curr->to];
    if(!to) {
        if(curr->to) Y[curr->idx-1] = -root->idx;
        else X[curr->idx-1] = -root->idx;
        curr->to ^= 1;
        walk(root, root, target, X, Y);
    }
    else if(to->terminal()) {
        if(curr->to) Y[curr->idx-1] = target;
        else X[curr->idx-1] = target;
        curr->to ^= 1;
    }
    else {
        if(curr->to) Y[curr->idx-1] = -to->idx;
        else X[curr->idx-1] = -to->idx;
        curr->to ^= 1;
        walk(to, root, target, X, Y);
    }
}

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    int depth = 31-__builtin_clz(N-1)+1;
    Node* root = construct(N, depth);
    vector<int> C(M+1);
    vector<int> X(counter, -10000), Y(counter, -10000);
    C[0] = A[0];
    for(int i = 1; i <= M; i++) C[i] = -1;
    for(int i = 1; i < N; i++) {
        walk(root, root, A[i], X, Y);
    }
    walk(root, root, 0, X, Y);
    answer(C, X, Y);
}

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