Submission #999560

#	Time	Username	Problem	Language	Result	Execution time	Memory
999560		phoenix	Mechanical Doll (IOI18_doll)	C++17	100 / 100	278 ms	14928 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(int l, int r, vector<int> a, vector<int> p) {
    if (a.empty()) {
        return -1;
    }   
    if (l == r) {
        return a[0];
    }
    int mid = (l + r) / 2;
    int m = (int)a.size();
    vector<int> la, lp, ra, rp;
    for (int i = 0; i < m; i++) {
        if (p[i] <= mid) {
            la.push_back(a[i]);
            lp.push_back(p[i]);
        } else {
            ra.push_back(a[i]);
            rp.push_back(p[i]);
        }
    }
    return create_switch(build(l, mid, la, lp), 
                        build(mid + 1, r, ra, rp));
}


void create_circuit(int M, vector<int> A) {
    int N = (int)A.size();

    vector<int> C(M + 1);
    C[0] = A[0];
    A.erase(A.begin());
    A.push_back(0);
    create_switch(-1, -1);
    
    int mxpw = 0;
    while ((1 << mxpw) < N) mxpw++;

    vector<int> p;
    for (int i = 0; i < N; i++) {
        int x = (1 << mxpw) - 1 - i;
        p.push_back(x);
    }
    auto rev = [&](int x) -> int {
        int res = 0;
        for (int i = 0; i < mxpw; i++) {
            res *= 2;
            if (x >> i & 1) res++;
        }
        return res;
    };
    sort(p.begin(), p.end(), [&](int a, int b) {
        return rev(a) < rev(b);
    });
    // cout << '{';
    // for (int c : A) 
    //     cout << c << ' ';
    // cout << '}';
    // cout << '\n';
    // cout << '{';
    // for (int c : p) 
    //     cout << c << ' ';
    // cout << '}';
    // cout << '\n';

    int root;
    root = build(0, (1 << mxpw) - 1, A, p);
    Y[0] = root;
    for (int i = 1; i <= M; i++) C[i] = root;
    
    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