Submission #288486

#	Time	Username	Problem	Language	Result	Execution time	Memory
288486		andrew	Mechanical Doll (IOI18_doll)	C++17	6 / 100	104 ms	11292 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 = 1e18;

ll stn = 0, id = -1;

vector <int> x, y, st;

int dfs(int tl, int tr){
    if(tl == tr)return st[tl];
    else{
        int tm = (tl + tr) >> 1;
        int t = stn, d = id;
        stn++;
        id--;
        x.p_b(0);
        y.p_b(0);
        x[t] = dfs(tl, tm);
        y[t] = dfs(tm + 1, tr);
        return d;
    }
}

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{
            C[i] = dfs(0, sz(st) - 1);
        }
    }

    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