Submission #1009661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009661		aaaaaarroz	Mechanical Doll (IOI18_doll)	C++17	47 / 100	101 ms	14800 KiB

doll

    #include "doll.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    int S = 0;
    vector<int> X, Y;
     
    int create_switch(int L, int R) {
        X.push_back(L);
        Y.push_back(R);
        S++;
        return -S;
    }
     
    int build(vector<int> v) {
        if ((int)v.size() == 1) {
            return v[0];
        }
        if (v[0] == -1 && v.back() == -1) {
            return -1;
        }
        int m = (int)v.size();
        int L, R;
        if (m & 1) {
            if (v.back()) {
                v.push_back(-1);
            } else {
                v.pop_back();
                v.push_back(-1);
                v.push_back(0);
            }
            m++;
        }
        vector<int> lv, rv;
        for (int i = 0; i < m; i++) {
            if (i & 1) rv.push_back(v[i]);
            else lv.push_back(v[i]);
        }
     
        L = build(lv);
        R = build(rv);
        return create_switch(L, R);
    }
     
    void create_circuit(int M, vector<int> A) {
        A.push_back(0);
        int t = A[0];
        A.erase(A.begin());
     
        create_switch(-1, -1);
        
        int root = build(A);
        Y[0] = root;
        vector<int> C(M + 1, root);
        C[0] = t;
        
        answer(C, X, Y);
    }

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