Submission #288512

#	Time	Username	Problem	Language	Result	Execution time	Memory
288512		andrew	Mechanical Doll (IOI18_doll)	C++17	6 / 100	129 ms	12316 KiB

doll

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

#define fi first
#define se second
#define p_b push_back
#define m_p make_pair
#define sz(x) (int)x.size()
#define pii pair <int, int>
#define all(x) x.begin(),x.end()

using namespace std;
typedef long long ll;
const ll inf = 1e7;

ll stn = 0, id = -1, uk;

vector <int> x, y, st, l, r, idx, le, ri;

int build(int v, int tl, int tr){
    le[v] = tl;
    ri[v] = tr;
    if(tl == tr)return 0;
    else{
        int tm = (tl + tr) >> 1;
        int t = stn, d = id;
        idx[v] = t;
        stn++;
        id--;
        l[v] = sz(l);

        l.p_b(0);
        r.p_b(0);
        le.p_b(0);
        ri.p_b(0);

        x.p_b(0);
        y.p_b(0);

        idx.p_b(0);

        r[v] = sz(l);

        l.p_b(0);
        r.p_b(0);
        le.p_b(0);
        ri.p_b(0);

        idx.p_b(0);
        int vv = build(l[v], tl, tm);
        x[t] = vv;
        vv = build(r[v], tm + 1, tr);
        y[t] = vv;
        return d;
    }
}

int dfs(int v){
    if(le[v] == ri[v])return st[uk++];
    else{
        int t = idx[v];
        int V = dfs(l[v]);
        if(V != inf)x[t] = V;
        swap(l[v], r[v]);
        swap(x[t], y[t]);
        return inf;
    }
}

void create_circuit(int M, vector<int> A) {
    int n = sz(A);
    stn = 0;
    id = -1;
    std::vector<int> C(M + 1);
    vector <vector <int>> v(M + 1);
    A.p_b(0);
    for(int i = 0; i < n; i++){
        v[A[i]].p_b(A[i + 1]);
    }
    C[0] = A[0];
    for(int i = 1; i <= M; i++){
        st = v[i];
        if(st.empty())C[i] = 0;
        else if(sz(st) == 1)C[i] = st[0];
        else{
            l.clear();
            le.clear();
            r.clear();
            ri.clear();
            uk = 0;
            l.p_b(0);
            le.p_b(0);
            r.p_b(0);
            ri.p_b(0);
            idx.p_b(0);
            C[i] = build(0, 0, sz(st) - 1);
            uk = 0;
            for(int i = 0; i < sz(st); i++){
                dfs(0);
            }
        }
    }

    answer(C, x, y);
}

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