Submission #254873

#	Time	Username	Problem	Language	Result	Execution time	Memory
254873		emil_physmath	Mechanical Doll (IOI18_doll)	C++17	100 / 100	156 ms	11896 KiB

doll

#include "doll.h"
#include <iostream>
using namespace std;
#define BUGO(x) cerr << #x << ": " << x << '\n';

int n, N;
vector<int> a;
int nodes;
vector<int> c, x, y, state;

int Solve(int l, int r)
{
    static int nodes = 0;
    if (r < N - n + 1 || l == r)
        return -1;
    int v = nodes++;
    x.resize(nodes); y.resize(nodes); state.resize(nodes);
    int m = (l + r) / 2;
    x[v] = -Solve(l, m) - 1;
    if (!x[v]) x[v] = -1;
    y[v] = -Solve(m + 1, r) - 1;
    if (!y[v]) y[v] = -1;
    return v;
}
void DFS(int v, int l, int r)
{
    static int trigger = 0;
    // cerr << " -> " << -v-1;
    if (v == 0 && (l != 1 || r != N))
        return;
    int m = (l + r) / 2;
    if (!state[v]) {
        state[v] = 1;
        if (l == m && l >= N - n + 1)
            x[v] = a[trigger++];
        else
            DFS(-x[v]-1, l, m);
    }
    else {
        state[v] = 0;
        if (m + 1 == r && r >= N - n + 1)
            y[v] = a[trigger++];
        else
            DFS(-y[v]-1, m + 1, r);
    }
}
void create_circuit(int M, std::vector<int> a_) {
    a = a_;
    a.push_back(0);
    n = a.size();
    N = 1;
    while (N < n)
        N *= 2;
    Solve(1, N);
    for (int i = 0; i < N; ++i)
        DFS(0, 1, N);
        // cerr << "DFS", DFS(0, 1, N), cerr << '\n';
    c.resize(M + 1);
    for (int i = 0; i <= M; ++i)
        c[i] = -1;
    answer(c, x, y);
}
/*
5 10
2 3 4 2 1 4 3 2 3 2
3 6
2 3 3 2 1 2
3 4
2 2 3 3
*/

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